The Ballad of James Weldon Demmel

by Beresford Parlett
with apologies to the poet Longfellow and Hiawatha

Two older friends had Weldon Demmel
Bound to him in closest union. And
to whom he gave the right hand
of his heart, in joy and sorrow.
Beresford, the curious Briton
And his deep advisor, Velvel.
Straight between them ran the pathway
Never grew the grass upon it.
Referees and jealous colleagues
Could not cause ill will between them.
For they kept each other’s council
Spake with naked hearts together
Pondering much and much contriving
How to solve our matrix problems.

To help all his people prosper
Jim shared the lead in LAPACK efforts.
He would choose the best of methods
For each type of matrix problem.
Then to implement each method
With respect to all platforms.
But all that work was very easy
Compared to what would follow next.
Testing, testing, always testing,
Until the lambs turn into sheep.
Then comes careful documentation
So the engineers could cope.
With how to use this precious software
To solve their practical equations
And ensure that their designs
Would always turn out to be stable,
But only just—to optimize.

Another issue haunted Demmel
As he surveyed the matrix land.
There were so many naughty problems
Ill-behaved, not dignified.
They would skip, react too sharply
Mis-converge and then mislead.
So the crafty, young Jim Demmel
Took his favorite canoe,
Made of birch-bark in the springtime,
And journeyed ever deeper to
This realm of troubled problems
Getting ever worse and worse.
At least he reached the dreaded chasm
Gateway to the underworld,
From which no person can return.
All the problems here are hopeless,
They can never be restored,
They are warped, defective, crippled
In a word, are SINGULAR.
He perceived that all nice problems
Stay far away from this dread place.
The closer to the chasm the worse the problems are.

Sometime later, Weldon Demmel taught
His people in this way:
Pointed at two (great) big Ms, saying;
If you can form their product quickly
Then you can solve all matrix problems
At this self same rapid rate.

The last exploit of Weldon Demmel
Was to find the primal code,
But this required an inward journey
Where no friends could lend a hand.
He meditated on group structures
To attain to Buddha hood.
He said good-bye to Kathy Yelick,
Bade farewell to Meg and Nate.
Then he ascended to Nirvana
Where ONE is all and all is ONE.
Space has vanished and, at last, No
COMMUNI-CA-TION.

The Lore Ax=b

by Erin Carson
Dedicated to Jim Demmel on the occasion of his 60th birthday
Inspired by the first lecture of Math 221

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!