Theoretical background of testing dgetrf

[michaellehn]

Hi,

I would like to learn more about the theoretical background of the tests performed
by the LAPACK test suite. For example, for testing dgetrf you are checking for

Screen Shot 2015-12-30 at 21.27.33.png (11.92 KiB) Viewed 12748 times

However, I haven't found any reference on the theoretical background for this. I assume
that this makes assumptions that the pivot growth is bounded in practical cases?

Cheers, Michael

[Julien Langou]

Hi Michael,

You are correct.

We assume more or less that the pivot growth is less than "thresh".

There is no theoretical justification, and actually we know this is not true for pathological matrices.

Note: Since n is rather small in the test suite and we know that the pivot growth is less than 2^(n-1) and we actually might be within the theory!!!

But more seriously, yes, we are assuming that pivot growth is bounded.

(We are not assuming that n is bounded by 5 . . . )

Best wishes, Julien.

[michaellehn]

Hi Julien,

thanks for the fast reply!

Michael

[michaellehn]

Sorry to bother again. I understand that for a test this criterion is sufficient. In the worst case it rejects a factorization even if it is numerically correct.

But just out of curiosity: I was looking up the error analysis in "Applied Numerical Linear Algebra" (Demmel). There it was shown that

Screen Shot 2015-12-30 at 23.11.50.png (10.54 KiB) Viewed 12743 times

So this couldn't be used to check if the factorization is correct? If I understand it correctly, the criterion

Screen Shot 2015-12-30 at 21.27.33.png (11.92 KiB) Viewed 12743 times

shows that the numerical method itself is backward stable for this particular matrix A. So it justifies using this method in this case and shows that the implementation is correct. So this is a good thing.

However, I wonder if I got that right: Using the above criterion would merely check if the factorization was computed "as correct as numerically possible" (even in cases dgetrf should not be used)?

So for pathological matrices like

Screen Shot 2015-12-30 at 22.15.46.png (11.92 KiB) Viewed 12743 times

were dgetrf is not "the right" choice the first criterion would accept the factorization and the second might not (for large n).

[Julien Langou]

Hi Michael,

Check #1: || A - PLU || < ( thresh ) . n . epsilon . || L || . || U ||
Check #2: || A - PLU || < ( thresh ) . n . epsilon . || A ||

Check #1 is true for any permutation. You do not have to permute and check #1 is true. You permute the row as you wish (partial pivoting, nothing, whatever) and check #1 is true. So, with check check #1, you are not checking the permutation scheme. If check #1 is true, you can do much with the factorization, for example, it is not enough to solve a linear system in backward stable sense. Check #1 is true for the matrix A = [ (10)^(-10) , 1; 1, 1 ] when we use LU factorization without pivoting. (And the factorization is garbage.) So check #1 is guaranteed for all permutation schemes but does not really help.

Check #2 checks for backward stability. LU factorization with partial pivoting fails check #2 for some pathological matrices (for example the matrix you give) but passes it otherwise. We say "practically backward stable".

So we check Check #2.

You write: "However, I wonder if I got that right: Using the above criterion (check #2) would check if the factorization was computed "as correct as numerically possible"?" => yes, this is a good way to put it. This is one way to explain the idea of backward stability. Checking backward stability is checking if a factorization is computed as correctly as numerically possible. One way to explain backward stability at a high level.

You write: "the first criterion would accept the factorization and the second might not (for large n)." => yes, this is a correct as well.

Best wishes,
Julien.