3 ms·
No. They're both O(N^3) in the dimension of the matrix. And it's more stable only in the sense that it's doing fewer operations. There's actually a great tri
by ajross 17y ago
No. They're both O(N^3) in the dimension of the matrix. And it's more stable only in the sense that it's doing fewer operations. There's actually a great trick (again, in Numerical Recipes) when doing inversion to spend a few more (constant factor) cycles to iterate a correction to the limit of the precision of your number representation.
Really, check Numerical Recipes. I like their section a lot, though I don't have my copy handy to give you a cite.
- petewarden 17y agoThey have old editions of Numerical Recipes online: http://www.nrbook.com/a/bookcpdf.php http://www.nrbook.com/a/bookcpdf.php Sadly they're using the horrid 'File open' encryption on the PDFs.
- jedbrown 17y agoThe asymptotics are completely different for sparse and banded matrices. And NR really isn't a good reference unless you are looking for a mildly flawed 30 year old analysis.
- ajross 17y agoNumerical Recipes has both sound theory exposition and working code (yes, with some bugs here and there). This blog post has neither. Nor, to my knowledge, does any other single reference out there. It's easily the best "how to think about numerics work" text I know; if you have a better one please point me there. It's easy for a wonk to flame about something as pedestrian as a how-to text for working scientists, but it's really not helpful.
- jedbrown 17y agoYou are probably familiar with this page http://www.fceia.unr.edu.ar/~fisicomp/apuntes/biblios/wnotnr.htm http://www.fceia.unr.edu.ar/~fisicomp/apuntes/biblios/wnotnr... and the suggested alternatives http://www.fceia.unr.edu.ar/~fisicomp/apuntes/biblios/altnr.htm http://www.fceia.unr.edu.ar/~fisicomp/apuntes/biblios/altnr.... In addition to those suggestions, here are a few more relevant to the present discussion. For dense matrices and how to think about linear algebra algorithms, I highly recommend Trefethen and Bau "Numerical Linear Algebra". For sparse direct solvers, Tim Davis' book (http://www.ec-securehost.com/SIAM/FA02.html http://www.ec-securehost.com/SIAM/FA02.html) is good, and you can transition from the "learning"-level implementation to Umfpack which is his production-quality solver (it's what is behind Matlab's backslash). For iterative solvers, Saad is pretty standard. For multiphysics solvers, I don't think any book can match the Knoll and Keyes' 2004 review on Jacobian-free Newton-Krylov methods (it's very accessible). The GSL has better implementations for many general-purpose algorithms in NR. SciPy is great if you work in Python. For scalable linear and nonlinear solvers, look at PETSc.
- chollida1 17y ago> And NR really isn't a good reference unless you are looking for a mildly flawed 30 year old analysis. Could you recommend a better book?
- eru 17y agoI guess I'll have to go back to my lecture notes. There was a reason why we did LU-decomposition (and similar things) instead of inverting matrices directly.