1function fl = luflops (L, U) 2%LUFLOPS compute the flop count for sparse LU factorization 3% 4% Example: 5% fl = luflops (L,U) 6% 7% Given a sparse LU factorization (L and U), return the flop count required 8% by a conventional LU factorization algorithm to compute it. L and U can 9% be either sparse or full matrices. L must be lower triangular and U must 10% be upper triangular. Do not attempt to use this on the permuted L from 11% [L,U] = lu (A). Instead, use [L,U,P] = lu (A) or [L,U,P,Q] = lu (A). 12% 13% Note that there is a subtle undercount in this estimate. Suppose A is 14% completely dense, but during LU factorization exact cancellation occurs, 15% causing some of the entries in L and U to become identically zero. The 16% flop count returned by this routine is an undercount. There is a simple 17% way to fix this (L = spones (L) + spones (tril (A))), but the fix is partial. 18% It can also occur that some entry in L is a "symbolic" fill-in (zero in 19% A, but a fill-in entry and thus must be computed), but numerically 20% zero. The only way to get a reliable LU factorization would be to do a 21% purely symbolic factorization of A. This cannot be done with 22% symbfact (A, 'col'). 23% 24% See NA Digest, Vol 00, #50, Tuesday, Dec. 5, 2000 25% 26% See also symbfact 27 28% Copyright 1998-2007, Timothy A. Davis 29 30 31Lnz = full (sum (spones (L))) - 1 ; % off diagonal nz in cols of L 32Unz = full (sum (spones (U')))' - 1 ; % off diagonal nz in rows of U 33fl = 2*Lnz*Unz + sum (Lnz) ; 34 35