87 views (last 30 days)

As I understand it, MATLAB's mldivide function uses a variety of algorithms to solve linear systems, performing various checks on the matrix involved to see what algorithm is applicable. These details are hidden from the user.

I recall that I have seen that there is some way to make MATLAB output the details of this procedure at runtime, where it prints out the result of the checks and the algorithm it decided on (LU, Cholesky, something from LAPACK even for sparse systems?). I can't find this information again despite my best attempts at searching these forums, the documentation, and the web. I know I have seen it somewhere. I was hoping someone here knows how to do this.

Failing this, can anyone tell me what algorithm mldivide would choose for the following? I have a pentadiagonal system in a sparse (2L x 2L) matrix for some whole number L

S = spdiags(myDiagonals,-2:2,2*L,2*L);

And a sparse right hand side with four nonzero entries.

b = spalloc(2*L,1,4);

Both contain complex entries in general and S it isn't symmetric or Hermitian or Toeplitz, but I'm not sure what other qualifiers might cause MATLAB to choose a specific algorithm. I calculate the inverse by

S\b

I appreciate any insights into what mldivide is doing in this case or how to get MATLAB to output the details of it's choice of algorithm. Thanks.

Grzegorz Knor
on 11 Dec 2013

See spparms function. For example:

A = sparse(diag(rand(5,1)))

spparms('spumoni',2)

A\rand(5,1)

produces:

sp\: bandwidth = 0+1+0.

sp\: is A diagonal? yes.

sp\: do a diagonal solve.

Or:

A = sparse(rand(10).*round(rand(10)-0.2));

spparms('spumoni',2)

A\rand(10,1)

porduces very long and detailed output:

sp\: bandwidth = 7+1+6.

sp\: is A diagonal? no.

sp\: is band density (0.35) > bandden (0.50) to try banded solver? no.

sp\: is A triangular? no.

sp\: is A morally triangular? no.

sp\: is A a candidate for Cholesky (symmetric, real positive diagonal)? no.

sp\: use Unsymmetric MultiFrontal PACKage with automatic reordering.

UMFPACK V5.4.0 (May 20, 2009), Control:

Matrix entry defined as: double

Int (generic integer) defined as: UF_long

0: print level: 2

1: dense row parameter: 0.2

"dense" rows have > max (16, (0.2)*16*sqrt(n_col) entries)

2: dense column parameter: 0.2

"dense" columns have > max (16, (0.2)*16*sqrt(n_row) entries)

3: pivot tolerance: 0.1

4: block size for dense matrix kernels: 32

5: strategy: 0 (auto)

6: initial allocation ratio: 0.7

7: max iterative refinement steps: 2

12: 2-by-2 pivot tolerance: 0.01

13: Q fixed during numerical factorization: 0 (auto)

14: AMD dense row/col parameter: 10

"dense" rows/columns have > max (16, (10)*sqrt(n)) entries

Only used if the AMD ordering is used.

15: diagonal pivot tolerance: 0.001

Only used if diagonal pivoting is attempted.

16: scaling: 1 (divide each row by sum of abs. values in each row)

17: frontal matrix allocation ratio: 0.5

18: drop tolerance: 0

19: AMD and COLAMD aggressive absorption: 1 (yes)

The following options can only be changed at compile-time:

8: BLAS library used: Fortran BLAS. size of BLAS integer: 8

9: compiled for MATLAB

10: CPU timer is ANSI C clock (may wrap around).

11: compiled for normal operation (debugging disabled)

computer/operating system: Microsoft Windows

size of int: 4 UF_long: 8 Int: 8 pointer: 8 double: 8 Entry: 8 (in bytes)

sp\: UMFPACK's factorization was successful.

sp\: However, UMFPACK may have failed to produce a correct factorization

possibly due to aggressive pivot tolerances or because the problem

is ill-conditioned.

sp\: These tolerances were:

Pivot Tolerance: 1.00e-01

Diagonal Pivot Tolerance: 1.00e-03

sp\: We will factor the matrix again but use standard partial pivoting.

sp\: UMFPACK's solve was successful.

UMFPACK V5.4.0 (May 20, 2009), Info:

matrix entry defined as: double

Int (generic integer) defined as: UF_long

BLAS library used: Fortran BLAS. size of BLAS integer: 8

MATLAB: yes.

CPU timer: ANSI clock ( ) routine.

number of rows in matrix A: 10

number of columns in matrix A: 10

entries in matrix A: 32

memory usage reported in: 16-byte Units

size of int: 4 bytes

size of UF_long: 8 bytes

size of pointer: 8 bytes

size of numerical entry: 8 bytes

strategy used: unsymmetric

ordering used: colamd on A

modify Q during factorization: yes

prefer diagonal pivoting: no

pivots with zero Markowitz cost: 1

submatrix S after removing zero-cost pivots:

number of "dense" rows: 0

number of "dense" columns: 0

number of empty rows: 1

number of empty columns 0

submatrix S not square or diagonal not preserved

symbolic factorization defragmentations: 0

symbolic memory usage (Units): 247

symbolic memory usage (MBytes): 0.0

Symbolic size (Units): 57

Symbolic size (MBytes): 0

symbolic factorization CPU time (sec): 0.00

symbolic factorization wallclock time(sec): 0.00

matrix scaled: yes (divided each row by sum of abs values in each row)

minimum sum (abs (rows of A)): 8.98358e-01

maximum sum (abs (rows of A)): 3.05977e+00

symbolic/numeric factorization: upper bound actual %

variable-sized part of Numeric object:

initial size (Units) 199 189 95%

peak size (Units) 978 947 97%

final size (Units) 33 30 91%

Numeric final size (Units) 124 116 94%

Numeric final size (MBytes) 0.0 0.0 94%

peak memory usage (Units) 1230 1199 97%

peak memory usage (MBytes) 0.0 0.0 97%

numeric factorization flops 1.65000e+02 3.60000e+01 22%

nz in L (incl diagonal) 27 16 59%

nz in U (incl diagonal) 37 29 78%

nz in L+U (incl diagonal) 54 35 65%

largest front (# entries) 49 12 24%

largest # rows in front 7 2 29%

largest # columns in front 7 6 86%

initial allocation ratio used: 0.7

# of forced updates due to frontal growth: 0

nz in L (incl diagonal), if none dropped 16

nz in U (incl diagonal), if none dropped 29

number of small entries dropped 0

nonzeros on diagonal of U: 9

min abs. value on diagonal of U: 0.00e+00

max abs. value on diagonal of U: 4.68e-01

estimate of reciprocal of condition number: 0.00e+00

indices in compressed pattern: 14

numerical values stored in Numeric object: 34

numeric factorization defragmentations: 1

numeric factorization reallocations: 1

costly numeric factorization reallocations: 1

numeric factorization CPU time (sec): 0.02

numeric factorization wallclock time (sec): 0.00

numeric factorization mflops (CPU time): 0.00

solve flops: 7.20000e+01

iterative refinement steps taken: 0

iterative refinement steps attempted: 0

solve CPU time (sec): 0.00

solve wall clock time (sec): 0.00

total symbolic + numeric + solve flops: 1.08000e+02

Opportunities for recent engineering grads.

Apply TodayFind the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
## 1 Comment

## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/85847-how-can-i-find-out-what-algorithm-mldivide-is-using#comment_355066

⋮## Direct link to this comment

https://www.mathworks.com/matlabcentral/answers/85847-how-can-i-find-out-what-algorithm-mldivide-is-using#comment_355066

Sign in to comment.