## Theoretical background of testing dgetrf

Open discussion regarding features, bugs, issues, vendors, etc.

### Theoretical background of testing dgetrf

Hi,

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 10588 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
michaellehn

Posts: 8
Joined: Tue Apr 13, 2010 2:59 pm

### Re: Theoretical background of testing dgetrf

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.
Julien Langou

Posts: 835
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA

### Re: Theoretical background of testing dgetrf

Hi Julien,

Michael
michaellehn

Posts: 8
Joined: Tue Apr 13, 2010 2:59 pm

### Re: Theoretical background of testing dgetrf

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 10583 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 10583 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 10583 times

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

Posts: 8
Joined: Tue Apr 13, 2010 2:59 pm

### Re: Theoretical background of testing dgetrf

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.
Julien Langou

Posts: 835
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA