The Lore Ax=b
Dedicated to Jim Demmel on the occasion of his 60th birthday
Inspired by the first lecture of Math 221 (see http://www.cs.berkeley.edu/~demmel/ma221_Fall14/Lectures/Lecture_01.html)
A typical day on Soda's fifth floor,
A student approaches and knocks on the door.
"Professor Demmel, please help," the student did plea,
"I need to solve the problem Ax=b."
"Alright," he said, with a patient reply,
"Just run simple GE if you haven't yet tried.
In terms of computation (ignore moving words),
its runtime is n cubed times constant two-thirds."
"That seems like a lot!", said the student, surprised.
"Well perhaps there's another approach we could try.
If your matrix is SPD it is true,
Cholesky will save you a factor of 2."
"That's still too expensive for me, I fear,
Since away from the diagonal nonzeros disappear."
"Ah," said the Professor, "not all is lost,
There's a banded version with a much cheaper cost."
"But since I only change b between solves, if I may,
suggest that I might precompute inverse A?"
"The inverse is dense and its use will be pesky.
You're better off saving the L from Cholesky."
"Hmm," thought the student, "Does it help that I know,
That there are at most seven nonzeros per row?"
"In that case," said the Professor, "forget methods direct,
As long as A's well-conditioned- have you checked?"
Consulting his notes, the student then shared,
"Kappa(A) is about the cube root of n squared."
"Well in that case, let's just use CG.
In flops it costs n raised to four over three."
"That still seems too much," the student did groan.
"Does it help if lambda_min and lambda_max are known?"
Professor Demmel pondered, scratching his head.
Are there details the student has still left unsaid?
"Perhaps more information will help guide our course,
This linear system - what is its source?"
"Well I've a cube of metal," the student replied,
"I know T on the surface but I need it inside!"
Professor Demmel smiled upon hearing this news,
For there were quite obvious methods to choose.
"That's just 3D Poisson, why didn't you say?
call FFT or multigrid and call it a day!"