Re: Is A\b using a sparse solver if A is sparse?

[David Bateman]

LUK ShunTim wrote:

> Hello,
>
> If A is sparse, will A\b automatically use the sparse variant of the
> linear equation solver?
>
> Regards,
> ST
> --
Yes.. In fact in 2.9.x it uses a polymorphic solver that has a selection 
tree

1. If the matrix is not square go to 9.
2. If the matrix is diagonal, solve directly and go to 9
3. If the matrix is a permuted diagonal, solve directly taking into
  account the permutations. Go to 9
4. If the matrix is banded and if the band density is less than that
  given by 'spparms ("bandden")' continue, else go to 5.
  4.a. If the matrix is tridiagonal and the right-hand side is not sparse
     continue, else go to 4b.
     4.a.1. If the matrix is hermitian, with a positive real diagonal, 
attempt
        Cholesky factorization using Lapack xPTSV.
     4.a.2. If the above failed, or the matrix is not hermitian, use 
Gaussian
        elimination with pivoting using Lapack xGTSV, and go to 9.
  4.b. If the matrix is hermitian with a positive real diagonal, attempt
     a Cholesky factorization using Lapack xPBTRF.
  4.c. if the above failed or the matrix is not hermitian with a positive
     real diagonal use Gaussian elimination with pivoting using
     Lapack xGBTRF, and go to 9.
5. If the matrix is upper or lower triangular perform a sparse forward
  or backward substitution, and go to 9
6. If the matrix is a upper triangular matrix with column permutations
  or lower triangular matrix with row permutations, perform a sparse 
forward
  or backward substitution, and go to 9
7. If the matrix is hermitian with a real positive diagonal, attempt
  a sparse Cholesky factorization using CHOLMOD.
8. If the sparse Cholesky factorization failed or the matrix is not
  hermitian, perform LU factorization using UMFPACK.
9. If the matrix is not square, or any of the previous solvers flags
  a singular or near singular matrix, find a minimum norm solution

At the moment I'm implementing the QR solver, and have it almost 
working, so the only step that doesn't work in this selction tree at the 
moment with the 2.9.x releases is step 9..

Regards
David

--
David Bateman                                address@hidden
Motorola Labs - Paris                        +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 6 72 01 06 33 (Mob) 
91193 Gif-Sur-Yvette FRANCE                  +33 1 69 35 77 01 (Fax) 

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------