L'U' = I+LU is as hard as general Ax=b

Summary

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(Nx) [x>=2], then you can solve an arbitrary Ax=b problem in order(Nx).

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 form L'U' = LU+I 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 as the factoring by converting Ax=b problem into the factor update problem (in order (N2) and then solving the resulting problem with the fast 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.

Permute the matrix

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 N2.

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 lower unit 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, 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 N2 you could sove Ax=b in time proportional to N2.

[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-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