Morally Triangular Matrices

Morally triangular matrices

Cleve Moler defines a matrix A as "morally triangular" if there exists a permutation P such that P*A is lower triangular. In contrast, John Gilbert defines a matrix A as "psychologically triangular" if there exist permutations P and Q such that P*A*Q is lower (or upper) triangular. Morally triangular matrices arise in MATLAB when you do [L,U]=lu(A); in this case, the partial pivoting is captured in L, which is morally triangular. The right factor, U, is simply triangular. Backslash then detects whether or not L is morally triangular when computing x=L\b, finds the permutation, and does the forward solve. Thus, in MATLAB:

    A = sprand (100,100,0.1) ;
    b = rand (100,1) ;
    [L,U] = lu (A) ;
    spparms ('spumoni',2) ;    % turn on sparse diagnostics
    x = L\b ;

you get the following output:

    sp\: bandwidth = 93+1+89.
    sp\: is A diagonal? no.
    sp\: is band density (0.34) > bandden (0.50) to try banded solver? no.
    sp\: is A triangular? no.
    sp\: is A morally triangular? yes.
    sp\: permute and solve.

I have a hard time keeping track of the difference between moral triangularity and psychological triangularity, and I suspect others who read the NA digest do too. Thus, in honor of Cleve and John, I wrote a helpful tool for remembering the difference:

Tweedle Tril and Tweedle Triu, by T.D.

I'm Tweedle Tril, he's Tweedle Triu.
We're the factors of sparse LU.
My brother: right and triangle;
Me? Triangularly moral.

If row i less than column j
gives L sub i j zero, say,
that does make me, it's very clear,
a matrix mere triangular.

Premultiply by P transpose;
pivot row swaps of L, suppose.
That's the process that gives to me
triangular morality.

But if my columns, one or all
for reasons psychological
are also swapped that makes me be
triangle psychologically.

I like my pivots small and sweet,
but the little pivots try me.
I watch my cholesterol and yet,
my chol ist err'd all high, I bet.

My brother likes his pivots large;
to which he's absolutely partial,
they say it keeps condition trim,
but to him they just give fill-in.

The pivots to which he's partial
keep my condition suitable.
My doctors math all want to show
condition number very low.

We're quite complete, as you can tell;
no preconditions, none at all.
Factor fine with no conditions,
yet we love those graph partitions.

And when at last we come to rest
and find solutions you can test,
Take norm resid and see it's best,
and note how low is our condest.

I don't think morally triangular matrices are related to the definition of "horror matrices", but in case they do, you can find the definition here.

If you like this poem, you can find more poems at Horror Matrices and Other Mathematical Poetry. Click here for an index of my serious poetry.