Rough Definition of "Online Algorithm"
In computer science an online algorithm is used to calculates a function of a set, but is fed its inputs incrementally instead of at once. As a rule they retains some sort of state which is bounded in size (rather than simply a set of all values seen up to that point).
If $f(x_1, \ldots, x_t)$ is the function to be evaluated at time $t$, then there should be some function $g$ and some sequences of states $(s_i)$ such that $$(f(x_1, \ldots, x_t), s_{t+1}) = g(x_t, s_{t})$$
Simple example of Online Algorithm
Here is an example using the average of a set of the numbers in Python2
state = {'total': 0, 'step': 0}
while True:
x = float(raw_input()) # get a number from the user
(avg, state) = g(x, state)
print avg
Where g is defined as
def g(x, state):
state['total'] = state['total'] + x
state['step'] = state['step'] + 1
avg = state['total'] / state['step']
return (avg, state)
Online algorithm for reduced row echelon form
A system of linear equations over the variables $\bar{x}$ can be thought of as a set of linear equations of the form $\bar{a} \cdot \bar{x} = b$.
I was wondering if there is a standard approach for streaming the linear equations so that at time $t$ the program is provided with $(\bar{a}_t, b_t)$ and calculates the current reduced row echelon form for all equations seen.
The most obvious solution is letting the state be the reduced row echelon form of all the equations known up to that point. When the new equation is introduced it is included it in the system of equations encoded in the reduced row echelon form and the program updates it state by gaussian elimination.
But this approach seems wasteful, and I am wondering if there is a smarter way to introduce the new equation.
I admit the state of this algorithm grows with the number of inputs. But it is bounded by the square of the number of variables of the overall system and does not grow unbounded with respect to the number of equations.