[Source](https://www.johndcook.com/blog/2010/01/20/ten-surprises-from-numerical-linear-algebra/ "Permalink to Ten surprises from numerical linear algebra")
# Ten surprises from numerical linear algebra
[ ![John D. Cook][1] ][2]
[Skip to content][3]
* [ABOUT][4]
* [SERVICES][5]
* [APPLIED MATH][6]
* [STATISTICS][7]
* [COMPUTATION][8]
* [WRITING][9]
* [BLOG][2]
* [TECHNICAL NOTES][10]
* [JOURNAL ARTICLES][11]
* [TWITTER][12]
* [PRESENTATIONS][13]
* [NEWSLETTER][14]
* [CLIENTS][15]
* [ENDORSEMENTS][16]
[(832) 422-8646][17]
[Contact][18]
# Ten surprises from numerical linear algebra
Posted on [20 January 2010][19] by [John][20]
Here are ten things about numerical linear algebra that you may find surprising if you’re not familiar with the field.
1. Numerical linear algebra applies very advanced mathematics to solve problems that can be stated with high school mathematics.
2. Practical applications often require solving enormous systems of equations, millions or even billions of variables.
3. The heart of Google is an enormous linear algebra problem. PageRank is essentially an eigenvalue problem.
4. The efficiency of solving very large systems of equations has benefited at least as much from advances in algorithms as from Moore’s law.
5. Many practical problems — optimization, differential equations, signal processing, etc. — boil down to solving linear systems, even when the original problems are non-linear. Finite element software, for example, spends nearly all its time solving linear equations.
6. A system of a million equations can sometimes be solved on an ordinary PC in under a millisecond, depending on the structure of the equations.
7. Iterative methods, methods that in theory require an infinite number of steps to solve a problem, are often faster and more accurate than direct methods, methods that in theory produce an exact answer in a finite number of steps.
8. There are many theorems bounding the error in solutions _produced on real computers_. That is, the theorems don’t just bound the error from hypothetical calculations carried out in exact arithmetic but bound the error from arithmetic as carried out in [floating point arithmetic][21] on computer hardware.
9. It is hardly ever necessary to compute the [inverse][22] of a matrix.
10. There is remarkably mature [software][23] for numerical linear algebra. Brilliant people have worked on this software for many years.
![Click to find out more about consulting for numerical computing][24]
**Related posts**:
* [Don’t invert that matrix][22]
* [Searching for John Francis][25]
* [Applying PageRank to biology][26]
* [Numerical computing consulting][27]
Categories : [Computing][28] [Math][29]
Tags : [Math][30] [Programming][31]
Bookmark the [permalink][32]
# Post navigation
Previous Post[Don’t invert that matrix][22]
Next Post[How to compute the soft maximum][33]
## 27 thoughts on “Ten surprises from numerical linear algebra”
1. Sean Devlin
[ 20 January 2010 at 10:53 ][34]
No love for ATLAS? I thought this was use in favor of lapack nowadays.
<http://math-atlas.sourceforge.net/>
2. Giles Warrack
[ 20 January 2010 at 11:31 ][35]
Re No 3, Herbert Wilf (Penn) has a nice handout on the Kendall-Wei algorithm and Google
<http://www.math.upenn.edu/~wilf/>
3. joeyo
[ 20 January 2010 at 12:27 ][36]
@Sean: LAPACK is built on top of BLAS/ATLAS.
4. Evan
[ 20 January 2010 at 22:48 ][37]
So.. you have convinced me to learn Linear Algebra. Do you have any suggestions for books to get started? Thanks for the inspiration!
5. John
[ 21 January 2010 at 00:11 ][38]
Evan, there are a lot of linear algebra books out there. I got a review copy of Cheney and Kincaid’s [ linear algebra book][39] a few weeks ago and I thought it was a nice text. It’s easy to read and has a good mix of theory and application.
If you know basic linear algebra and want to jump into numerical linear algebra, I recommend Demmel’s [Applied Numerical Linear Algebra][40]. Also, there’s the classic [Matrix Calculations][41] by Golub and Van Loan.
6. Evan
[ 21 January 2010 at 14:54 ][42]
John, thanks for your quick reply. I’ll definitely check those out!
7. Matt
[ 24 January 2010 at 06:46 ][43]
By the way, has anyone here played with GotoBLAS?
Is its performance really as good as the benchmarks on its website suggest or is it just advertisement?
The source code is freely available, though only for research applications (commercial is not free). Here are relevant links:
We recently released a MATLAB package called QLA that dramatically accelerates core linear algebra routines on dense matrices. It includes SVD, linear systems, least squares, PCA, etc., and speedups range from 10x to 1,000x+ on benchmarks. The gains come by trading a minuscule bit of accuracy for a mammoth increase in speed.
You can find more details and the free beta version here:
<http://massiveanalytics.com>.
9. Ron Modesitt
[ 26 July 2010 at 18:46 ][45]
What a thoroughly interesting blog! Glad I found you, with thanks to Stumble.
Ron
10. [Luis][46]
[ 19 July 2011 at 17:45 ][47]
Another interesting surprise is that, often, the matrices involved are very sparse.
Books: I love “Matrix algebra useful for statistics” by Searle.
11. fish
[ 13 September 2011 at 11:32 ][48]
Ha, good to know re: matrix inversion — I often use inverts in calculating color transforms (see <http://www.brucelindbloom.com/index.html?Eqn_RGB_XYZ_Matrix.html>) but hey. Thanks!
12. [Utkarsh Upadhyay][49]
[ 13 September 2011 at 11:02 ][50]
Some surprises indeed!
However, a small note for point 4:
> The efficiency of solving very large systems of equations has benefited at least as much from advances in algorithms as from Moore's law.
At least solutions for spare system of equations have benefited [two orders of magnitude more from algorithmic developments than hardware advancements][51] (slide 7) to a total of _10 orders of magnitude improvement_ from 1970 to 2001.
For other kinds of linear equations, the improvements [ indeed have been approximately the same.][52].
13. Juan Solano
[ 13 September 2011 at 11:33 ][53]
Let me recommend the videos in Khan Academy, is a very nice place to start and refresh the key concepts.. and then digest the Linear Algebra beauty…
<http://www.khanacademy.org/#browse>
Juan
14. J
[ 13 September 2011 at 12:18 ][54]
Charles Van Loan has a sweet pair of custom Nike kicks. Not even joking.
15. [martin][55]
[ 13 September 2011 at 15:53 ][56]
Could you elaborate on number 6? I would have thought it would have taken close to a millisecond to just read a million values.
16. mg
[ 13 September 2011 at 17:07 ][57]
@Evan my favorite text is Janich’s Linear Algebra.
17. Evan
[ 13 September 2011 at 17:16 ][58]
Thanks mg. I’ll check that out as well.
18. AV
[ 14 September 2011 at 04:20 ][59]
this article is a ‘trivality’.
any indian schoolkid knows this.
– of course linear algebra is balzing fast for FEA and related computations.
but the writer should state that the ‘speed’ in fast lin algebra comes not from inherent properties of lin-algebra, but from the fact that we MASSIVELY approximate the actual behavior of the beams/trusses/etc. we approximate reality. and thats becoz we dont have good computational algos to handle the ‘true’ mathematical representations.
if that was ‘overhead transmission’– then here’s a simplification– try to find a ‘fast’ solution to the Navier Stokes equations using ‘linear algebra’– in their pure form.
19. Anselmo
[ 19 November 2011 at 20:48 ][60]
For me, the greatest achievement of linear algebra is the simplex method. Linear optimisation problems with million variables may be solved in home computers in a few minutes. It is remarkably efficient, though it has an exponential worst case performance. In addition, most exact non-linear optimisation algorithms use the simplex method for solving the linear approximation model.
20. babita
[ 19 May 2012 at 09:02 ][61]
i want to solve the equation Ax=B,where A is sparse given in CSC format.A and B are known.
Can you give me some references to solve it???
Reply as soon as possible…its urgent..
21. Pingback: [Ten surprises from numerical linear algebra | mathcsteacher][62]
22. Federico Poloni
[ 13 February 2013 at 12:49 ][63]
“The heart of Google is an enormous linear algebra problem.”
This is often heard, and the algorithm itself is a nice one to tell around, but I think its role in the architecture of a search engine is overrated.
1- While PageRank constitutes a part of the algorithm that is used to rank sites (allegedly – it’s not like it’s open source), there must be much more than that. PageRank returns a universal ranking, that does not depend on the query. Clearly the ordering has to be tweaked to the specific search. Pagerank is not computed on-the-fly for every web search, it would be too slow to do that.
2- Ranking isn’t the only part of the problem. There is crawling, indexing, storing data, and recalling results efficiently. PageRank might be a nice idea that constitutes 1% of that, but the bulk of the computation is many boring details on storing and retrieving compressed data.
23. John
[ 13 February 2013 at 13:37 ][64]
Frederico: The basic idea that made Google a better search engine than competitors was an eigenvalue problem. That’s not to say that the algorithm hasn’t been tweaked, or that it’s easy to implement, or that many other factors don’t matter.
24. Pingback: [Iterative linear solvers as metaphor | John D. Cook][65]
25. Pingback: [Don’t invert that matrix][66]
26. Pingback: [Three surprises with the trapezoid integration rule][67]
27. Pingback: [Linear solvers are behind lattice QCD – PRACE Summer Of HPC][68]
### Leave a Reply [Cancel reply][69]
Your email address will not be published. Required fields are marked *
Comment
Notify me of followup comments via e-mail
Name *
Email *
Website
Search for:
![John D. Cook][70]
**John D. Cook, PhD**
# Latest Posts
* [Fibonacci / Binomial coefficient identity][71]
* [Painless project management][72]
* [New animation feature for exponential sums][73]
[32]: https://www.johndcook.com/blog/2010/01/20/ten-surprises-from-numerical-linear-algebra/ "Permalink to Ten surprises from numerical linear algebra"
[71]: https://www.johndcook.com/blog/2018/02/22/fibonacci-binomial-coefficient-identity/ "Permanent link to Fibonacci / Binomial coefficient identity"
[72]: https://www.johndcook.com/blog/2018/02/20/painless-project-management/ "Permanent link to Painless project management"
[73]: https://www.johndcook.com/blog/2018/02/19/new-animation-feature-for-exponential-sums/ "Permanent link to New animation feature for exponential sums"
[74]: https://www.johndcook.com/blog/2018/02/19/quantifying-normal-approximation-accuracy/ "Permanent link to Quantifying normal approximation accuracy"
[75]: https://www.johndcook.com/blog/2018/02/17/ordinary-potential-polynomials/ "Permanent link to Ordinary Potential Polynomials"
