In Intro to Linear Algebra by Gilbert Strang (page 102, version 5), he says:

"Most matrices in practice are sparse (many zero entries). In these cases, A = LU is much faster".

Now, I understand completely that LU factorization helps when you want to evaluate multiple $b$ in $Ax=b$. You basically "cache" the information of A into $L$ and $U$ which allows you to solve $AX=b$ for novel $b$ in quadratic vs cubic runtime w.r.t. the matrix width/height.

HOWEVER: The way Strang words this part sounds like he is referring to something else entirely. It's almost like he's saying for a single run of $Ax=b$, when A is huge and sparse, LU decomposition is faster. I see no reason why that is the case. In Gauss Jordan if you have a band-matrix A you can still "skip" sections of the computations if you know there will be swaths of zeros.

Can someone explain what he means?

  • 1
    $\begingroup$ There is a huge literature on linear algebra algorithms specifically designed for sparse matrices. my guess is that he knows of some algorithm for sparse-LU with a faster runtime than sparse-Gauss-Jordan. Unfortunately I don't know of the sparse algorithms specifically $\endgroup$
    – Zim
    Jun 22, 2020 at 3:10
  • $\begingroup$ @Zim If he meant some other algorithm beyond the basic LU he described in the book, he should've explained that more clearly, because right now it seems like he's saying standard LU decomp allows you to quickly solve Ax=b. $\endgroup$
    – user3180
    Jun 24, 2020 at 1:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.