Given a unit lower triangular matrix, and a unit upper triangular matrix U,
if you can find a new tringular matrices L' and U' (not necessarily
triangular) such that L'U'=(I+LU), in time order(N^{x}) [x>=2],
then you can solve an arbitrary Ax=b problem in order(N^{x}).

Triangular systems can be solved in order N^{2} time.

Since reading the data in Ax=b or (LU) is order N^{2}, there can
not be a method of solving either faster then N^{2}.

We will prove that any general Ax=b problem can be converted to a
factoring update problem of the form L'U' = LU+I in order N^{2}
time. And if there were a solution to the factor update problem
any faster then that of the general Ax=b problem, it could be used to
solve the Ax=b problem in the same order of complexity as the factoring
by converting Ax=b problem into the factor update problem (in order
(N^{2}) and then solving the resulting problem with the fast factor
update method.

- permute matrix to get a non-zero diagonal
[Order (N
^{2})] - Scale the matrix [Order (N
^{2}] - Split the matrix into the
**sum**of two matrices of the right form. [Order (N^{2})] - Setup [Order (N
^{2})] - Do factor update [Order ?]
- Solve the resulting triangular system
[Order (N
^{2})]

Since all the steps are order (N^{2}) except for an unknown
cost for the factor update step, and the factor update can not be
less than order (N^{2}), the cost of solving Ax=b by this method
is just on the order of whatever the cost of the factoring update is.

So now we just need to flesh out the individual steps above.

We need to permute the matrix so that we have non-zero elements on
the diagonal. For each row this involves a swap of two elements, which
one might guess makes it order N, but the decision of which to swap
requires (in worst case) N compares, so the result is order N^{2}.

Next, we scale the matrix rows to make each diagonal element have the
value 2. Since scaling a row involves N operations, and there are N rows,
this is obviously order (N^{2}) work. And since in the previous
step we made sure that all diagonal elements were non-zero, we know it is
posible.

This can be done by the following (order N^{2}) process:

- Copy the elements below the diagonal in A to L
- Copy the elements above the diagnoal in A to U
- Since each diagonal element has value 2, and 2 = 1+1, the diagonal elements of both U and L can be set to 1.

We now have unit triangular lower L and unit upper triangular U.
And this procedure is clearly order N^{2}.

Since L is unit lower triangular, we know it is non-singular, and it can
be inverted. L^{-1} is also unit lower triangular. So one could
pre-multiply both sides of the equation by L^{-1}:

L^{-1}(L + U)x = L^{-1}b == (I+L^{-1}U)x = L^{-1}b

The right hand side can be computed in order N^{2} time,
and the left hand side is just a formal setup into show that we have a
problem of the form I+LU. (And therefore needs no explicit arithmetic,
since we aren't going to multiply it out.)

Compute new L and U (triangular, but no longer necessarily unit triangular) factors (L' and U') from (I+LU) by whatever allegedly fast algorithm you have. This gives a new problem:

L'U'x=L^{-1}b

Since the system now has ONLY triangular matrices, it can now be solved
in N^{2} time with standard algorithms.

We have now fleshed out all of the steps sketched out above, and have proven that the Ax=b problem can be solved with on the order of the same cost as the factor update problem for (I+LU). And therefore the (I+LU) update can not have a cost any lower than solving full Ax=b problem.

Therefore, any "fast" I+LU factor update algorithm, leads constructively
to an algorithm to sove Ax=b with a time of the same order. So, for
example, If you could solve L'U'=(I+LU) in time proportional to
N^{2} you could sove Ax=b in time proportional to N^{2}.

[Assuming, of course, that I've not blotched it somewhere above.]

This page is http://www.cc.utah.edu/~nahaj/math/ilu.html © Copyright 2003-2010 by John Halleck, All Rights Reserved. This snapshot was last modified on August 19th, 2011 And the underlying file was last modified on December 15th, 2008