I+LU is as hard as Ax=b

Summary

Given a unit lower triangular matrix, and an upper triangular matrix U, the problem of forming a new updated L and U after adding the identity (I + LU) is as expensive as the problem of solving a general linear system (Ax=b).

Assumptions

Triangular systems can be solved in order N2 time.

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

Proof

We will prove that any general Ax=b problem can be converted to a factoring update problem of the given form in order N2 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 by converting Ax=b problem into the factor update problem (in order (N2) and then solve the resulting problem with the factor update method.

Outline

Since all the steps are order (N2) except for an unknown cost for the factor update step, and the factor update can not be less than order (N2), 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.

Scale the matrix so that all diagonal elements have value 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 (N2) work. And since in the previous step we made sure that all diagonal elements were non-zero, we know it is posible.

Split the matrix into the SUM of two unit triangular matrices L and U

Any arbitrary square matrix that has only 2's on the diagonals can be split into the *SUM* of a unit lower triangular matrix and an upper unit triangular matrix (A = L + U) in order N2 time. (Note that we really do intend here the sum and not the product.)

This can be done by the following (order N2) process:

  1. Copy the elements below the diagonal in A to L
  2. Copy the elements above the diagnoal in A to U
  3. 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 N2.

Setup

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-1b
==
   (I+L-1U)x   = L-1b

The right hand side can be computed in order N2 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.)

Factor Update

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-1b

Solve the system

Since the system now has ONLY triangular matrices, it can now be solved in N2 time with standard algorithms.

Conclusion

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, the I+LU factor update problem for unit L and U is at least as difficult as solving the full blown Ax=b problem.

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

Go to ...

This page is http://www.cc.utah.edu/~nahaj/math/ilu.html
© Copyright 2003 by John Halleck, All Rights Reserved.
This snapshot was last modified on February 19th, 2008