Another patch for the manual

[David Bateman]

Since Soren started sending patches to the manual, I thought I'd add
one.. This patch discusses briefly the selection tree used to determine
which factorization is used for the solution of a linear equation or
matrix inverse...

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

*** ./doc/interpreter/linalg.txi.orig7  2007-04-11 11:30:15.092619920 +0200
--- ./doc/interpreter/linalg.txi        2007-04-11 11:32:19.067901925 +0200
***************
*** 11,21 ****
--- 11,69 ----
  1989, and in @address@hidden Users' Guide}, SIAM, 1992.
  
  @menu
+ * Techniques used for Linear Algebra::
  * Basic Matrix Functions::      
  * Matrix Factorizations::       
  * Functions of a Matrix::       
  @end menu
  
+ @node Techniques used for Linear Algebra
+ @section Techniques used for Linear Algebra
+ 
+ Octave includes a poly-morphic solver, that selects an appropriate
+ matrix factorization depending on the properties of the matrix itself. 
+ Generally, the cost of determining the matrix type is small relative to 
+ the cost of factorizing the matrix itself, but in any case the matrix 
+ type is cached once it is calculated, so that it is not re-determined 
+ each time it is used in a linear equation.
+ 
+ The selection tree for how the linear equation is solve or a matrix
+ inverse is form is given by
+ 
+ @enumerate 1
+ @item If the matrix is upper or lower triangular sparse a forward or
+ backward substition using the @sc{Lapack} xTRTRS function, and goto 4.
+ 
+ @c Permuted triangular matrices currently disabled in the code
+ @c
+ @c @item If the matrix is a upper triangular matrix with column permutations
+ @c or lower triangular matrix with row permutations, perform a forward or
+ @c backward substitution, and goto 5.
+ 
+ @item If the matrix is square, hermitian with a real positive diagonal,
+ attempt Cholesky factorization using the @sc{Lapack} xPOTRF function.
+ 
+ @item If the Cholesky factorization failed or the matrix is not
+ hermitian with a real positive diagonal, and the matrix is square, factorize 
+ using the @sc{Lapack} xGETRF function.
+ 
+ @item  If the matrix is not square, or any of the previous solvers flags
+ a singular or near singular matrix, find a least squares solution using
+ the @sc{Lapack} xGELSS function.
+ @end enumerate
+ 
+ The user can force the type of the matrix with the @code{matrix_type}
+ function. This overcomes the cost of discovering the type of the matrix.
+ However, it should be noted incorrectly identifying the type of the matrix
+ will lead to unpredictable results, and so @code{matrix_type} should be
+ used with care.
+ 
+ It should be noted that the test for whether a matrix is a candidate for
+ Cholesky factorization, performed above and by the @code{matrix_type}
+ function, does not give a certainty that the matrix is
+ Hermitian. However, the attempt to factorize the matrix will quickly
+ flag a non-Hermitian matrix.
+ 
  @node Basic Matrix Functions
  @section Basic Matrix Functions
  
***************
*** 35,40 ****
--- 83,90 ----
  
  @DOCSTRING(inv)
  
+ @DOCSTRING(matrix_type)
+ 
  @DOCSTRING(norm)
  
  @DOCSTRING(null)
*** ./doc/interpreter/sparse.txi.orig7  2007-04-11 11:30:22.202234996 +0200
--- ./doc/interpreter/sparse.txi        2007-04-11 11:31:12.500510599 +0200
***************
*** 1425,1432 ****
  @emph{Not implemented}
  @item eigs
  @emph{Not implemented}
- @item @ref{matrix_type}
- Identify the matrix type or mark a matrix as a particular type.
  @item @ref{normest}
  Estimates the 2-norm of the matrix @var{a} using a power series analysis.
  @item @ref{spchol}
--- 1425,1430 ----
***************
*** 1538,1545 ****
                matrix.
  * luinc::     Produce the incomplete LU factorization of the sparse 
                A.
- * matrix_type:: Identify the matrix type or mark a matrix as a particular
-               type.
  * normest::   Estimates the 2-norm of the matrix @var{a} using a power 
                series analysis.
  * nnz::       returns number of non zero elements in SM See also: sparse
--- 1536,1541 ----
***************
*** 1656,1673 ****
  
  @DOCSTRING(issparse)
  
! @node luinc, matrix_type, issparse, Function Reference
  @subsubsection luinc
  
  @DOCSTRING(luinc)
  
! @node matrix_type, normest, luinc, Function Reference
! @subsubsection matrix_type
! 
! @DOCSTRING(matrix_type)
! 
! 
! @node normest, nnz, matrix_type, Function Reference
  @subsubsection normest
  
  @DOCSTRING(normest)
--- 1652,1663 ----
  
  @DOCSTRING(issparse)
  
! @node luinc, normest, issparse, Function Reference
  @subsubsection luinc
  
  @DOCSTRING(luinc)
  
! @node normest, nnz, luinc, Function Reference
  @subsubsection normest
  
  @DOCSTRING(normest)
*** ./doc/interpreter/octave.texi.orig7 2007-04-11 11:32:49.827233310 +0200
--- ./doc/interpreter/octave.texi       2007-04-11 11:32:23.388667576 +0200
***************
*** 380,385 ****
--- 380,386 ----
  
  Linear Algebra
  
+ * Techniques used for Linear Algebra::
  * Basic Matrix Functions::      
  * Matrix Factorizations::       
  * Functions of a Matrix::