Theoretical background of testing dgetrf

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

Theoretical background of testing dgetrf

Postby michaellehn » Wed Dec 30, 2015 4:58 pm

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
Screen Shot 2015-12-30 at 21.27.33.png (11.92 KiB) Viewed 10595 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

Postby Julien Langou » Wed Dec 30, 2015 5:03 pm

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

Postby michaellehn » Wed Dec 30, 2015 5:30 pm

Hi Julien,

thanks for the fast reply!

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

Re: Theoretical background of testing dgetrf

Postby michaellehn » Wed Dec 30, 2015 6:33 pm

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
Screen Shot 2015-12-30 at 23.11.50.png (10.54 KiB) Viewed 10590 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
Screen Shot 2015-12-30 at 21.27.33.png (11.92 KiB) Viewed 10590 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
Screen Shot 2015-12-30 at 22.15.46.png (11.92 KiB) Viewed 10590 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

Postby Julien Langou » Thu Dec 31, 2015 12:56 am

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


Return to User Discussion

Who is online

Users browsing this forum: No registered users and 6 guests

cron