[scilab-Users] \ and / and inv() algorithm

[Michaël Baudin]

Hi,

In most cases, the backslash operator uses a Gaussian elimination with 
row pivoting. In some cases, it uses a least squares algorithm.

See in "Programming in Scilab" :

http://forge.scilab.org/index.php/p/docprogscilab/downloads/

section 5.6, "References and notes".

"In the section 5.1.3, we presented a Gaussian elimination algorithm and 
stated
134 that this algorithm (but not the particular implementation that we 
presented) is
used in Scilab, behind the backslash operator. The actual behavior of 
the backslash
operator in Scilab is the following. First, we perform a call to the 
DGETRF LAPACK
routine, which decomposes the matrix A into PA = LU, where P is a 
permutation
matrix, L is a lower triangular matrix and U is an upper triangular 
matrix. The
diagonal entries of L are unity. Then we call the DGECON LAPACK routine, 
which
approximates the inverse of the 1-norm condition number of the matrix A. 
At this
point, there are two cases. If the condition number of the matrix is not 
too large,
then the system of linear equations is not ill-conditioned (this is not 
exact, because
the condition is only approximated, but the algorithms makes the 
hypothesis that
the estimation can be trusted). In this case, we call the DGETRS LAPACK 
routine,
which solves the linear system of equations by using the PA = LU 
decomposition.
More precisely, this step uses row permutations, and then the forward 
and backward
substitutions in order to compute the solution x depending on the 
right-hand side b.
In the other case, that is, if the matrix is ill-conditioned, we use a 
modi
fied version
of the DGELSY LAPACK routine, which solves the associated least-squares 
problem.
This choice may reduce the accuracy for matrices of intermediate 
condition [9]."

The inv function just solves the equation Ax=b with b=eye(A), so that it 
is just a particular call to essentially algorithms. Actually, the 
algorithm that you can find in :

http://gitweb.scilab.org/?p=scilab.git;a=blob;f=scilab/modules/linear_algebra/src/fortran/intdgetri.f;h=061fe92c5fbae006485493df93c77b8c26a59843;hb=HEAD

uses another routine, DGETRI:

http://www.netlib.org/lapack/double/dgetri.f

Best regards,

Michaël

Le 14/01/2011 11:35, w_artichowicz a écrit :
> Hello,
>
> I would like to find out what algorithm is used to estimate the inverse matrix when using operators
>
> \ or /
>
> or function inv().
>
>
> Thanks in advance.
>


-- 
Michaël Baudin
Ingénieur de développement
michael.baudin at scilab.org
-------------------------
Consortium Scilab - Digiteo
Domaine de Voluceau - Rocquencourt
B.P. 105 - 78153 Le Chesnay Cedex
Tel. : 01 39 63 56 87 - Fax : 01 39 63 55 94