8.0.0.3. Linear Algebra
|
(packages/libnum/linalgebra.lsh) |
This provides such things as linear system solving, matrix inverse,
eigenvalues of symmetric matrices, and singular value decomposition for
real and complex matrices. Most functions have two version, a
"high-level" version (generally a macro) which allocates and returns
results and does not touch the input arguments, and "low-level" version
which writes results into pre-allcoated arguments and which may
overwrite the content of input arguments. The low-level versions avoid
allocation and copy that may be unnecessary. They are identified with
the -inplace suffix to the name.
8.0.0.3.0. eigenvalues, eigenvectors
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.0.0. (eigen-symm m)
|
(packages/libnum/linalgebra.lsh) |
Compute eigenvalues of symmetric real matrix m
. The vector of eigenvalues in descending order is returned.
8.0.0.3.0.1. (eigen-symmv m eigenvec)
|
(packages/libnum/linalgebra.lsh) |
Compute eigenvalues of symmetric real matrix m
. A vector of sorted eigenvalues is returned, and the eigenvectors are
written in matrix eigenvec .
8.0.0.3.0.2. (eigen-herm m)
|
(packages/libnum/linalgebra.lsh) |
Compute eigenvalues of Hermitian complex matrix m
. A vector of sorted eigenvalues is returned.
8.0.0.3.0.3. (eigen-hermv m eigenvec)
|
(packages/libnum/linalgebra.lsh) |
Compute eigenvalues of Hermitian complex matrix m
. A vector of sorted eigenvalues is returned.
8.0.0.3.1. matrix decompositions (SVD, LU cholesky, QR, tridigonal, householder).
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.1.0. SVD: singular value decomposition
|
(packages/libnum/linalgebra.lsh) |
[from the GSL manual]: A general rectangular MxN
matrix A has a singular value
decomposition (SVD) into the product of an MxN
orthogonal matrix U , an
NxN diagonal matrix of singular values
S and the transpose of an NxN
orthogonal square matrix V ,
A = U S V^T The singular values Si =
Sii are all non-negative and are generally chosen to form a
non-increasing sequence S1, S2...Sn .
The singular value decomposition of a matrix has many practical uses.
The condition number of the matrix is given by the ratio of the largest
singular value to the smallest singular value. The presence of a zero
singular value indicates that the matrix is singular. The number of
non-zero singular values indicates the rank of the matrix. In practice
singular value decomposition of a rank-deficient matrix will not produce
exact zeroes for singular values, due to finite numerical precision.
Small singular values should be edited by choosing a suitable tolerance.
8.0.0.3.1.0.0. (svd A V S)
|
(packages/libnum/linalgebra.lsh) |
[from the GSL manual]: This function factorizes the
MxN matrix A into the
singular value decomposition A = U S V^T
. On output the matrix U is returned. The diagonal elements of the
singular value matrix S are stored in
the vector S . The singular values are
non-negative and form a non-increasing sequence from
S1 to SN . The matrix
V contains the elements of V
in untransposed form. To form the product U S V^T
it is necessary to take the transpose of V
. This routine uses the Golub-Reinsch SVD algorithm. Example:
(setq a [[1 2][3 4][5 6]])
(setq v (double-matrix 2 2))
(setq s (double-matrix 2))
(svd a v s)
8.0.0.3.1.1. LU decomposition
|
(packages/libnum/linalgebra.lsh) |
[from the GSL manual] A general square matrix A has an LU decomposition
into upper and lower triangular matrices, PA = LU
, where P is a permutation matrix,
L is unit lower triangular matrix and
U is upper triangular matrix. For square matrices this
decomposition can be used to convert the linear system
Ax = b into a pair of triangular systems
Ly = P b, U x = y , which can be solved by forward and
back-substitution. Note that the LU decomposition is valid for singular
matrices.
The following functions factorize the square matrix
a into the LU decomposition PA = LU
. On output the diagonal and upper triangular part of the argument
lu contain the matrix U, and the lower triangular part
(excluding the diagonal) contains L. The diagonal elements of L are
unity, and are not stored. The permutation matrix P is encoded in the
permutation argument p , which is an
idx1 of int. The j-th column of the matrix P is given by the k-th column
of the identity matrix, where k = pj
the j-th element of the permutation vector. The sign of the permutation
is returned as an int. It has the value (-1)^q
, where q is the number of
interchanges in the permutation. The algorithm used in the decomposition
is Gaussian Elimination with partial pivoting (Golub & Van Loan, Matrix
Computations, Algorithm 3.4.1).
8.0.0.3.1.1.0. (lu-decomp a p lu)
|
(packages/libnum/linalgebra.lsh) |
Compute LU decomposition of real square matrix a
, put result in lu , and permutation
in p , which must an idx1 of int. The
parity of the permutation is returned as an int.
8.0.0.3.1.1.1. (lu-decomp-complex a p lu)
|
(packages/libnum/linalgebra.lsh) |
Compute LU decomposition of real square matrix a
, put result in lu , and permutation
in p , which must an idx1 of int. The
parity of the permutation is returned as an int.
8.0.0.3.1.2. Cholesky decomposition
|
(packages/libnum/linalgebra.lsh) |
[from the GSL manual] A symmetric, positive definite square matrix
A has a Cholesky decomposition into a product of a lower
triangular matrix L and its transpose
LT , A=LL' This is
sometimes referred to as taking the square-root of a matrix. The
Cholesky decomposition can only be carried out when all the eigenvalues
of the matrix are positive. This decomposition can be used to convert
the linear system Ax = b into a pair
of triangular systems (Ly = b, LT x = y)
, which can be solved by forward and back-substitution.
8.0.0.3.1.2.0. (cholesky-decomp A)
|
(packages/libnum/linalgebra.lsh) |
This function factorizes the positive-definite square matrix
A into the Cholesky decomposition A =
LL' and returns the results. In the returned matrix, the
diagonal and lower triangular part contain the matrix
L . The upper triangular part contains
L' , the diagonal terms being identical for both
L and L' . If the matrix is
not positive-definite then the decomposition fails and the function
returns nil.
8.0.0.3.2. solution of linear systems.
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.2.0. (solve-sv a b)
|
(packages/libnum/linalgebra.lsh) |
This function solves a (possibly non-square) system
A x = b in the least-square sense using the singular value
decomposition.
8.0.0.3.2.1. (solve-hh a b)
|
(packages/libnum/linalgebra.lsh) |
This function solves the system A x = b using the Householder
transformations. The solution is returned.
8.0.0.3.2.2. (solve-lu a b)
|
(packages/libnum/linalgebra.lsh) |
This function solves the system A x = b using the LU decomposition. The
solution is returned.
8.0.0.3.2.3. (solve-lu-complex a b)
|
(packages/libnum/linalgebra.lsh) |
This function solves the complex system A x = b using the LU
decomposition. The solution is returned.
8.0.0.3.3. matrix inverse
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.3.0. (inverse-lu a)
|
(packages/libnum/linalgebra.lsh) |
return the inverse of square matrix a
, computed using LU decomposition.
8.0.0.3.3.1. (inverse-lu-complex a)
|
(packages/libnum/linalgebra.lsh) |
return the inverse of square complex matrix a
, computed using LU decomposition.
8.0.0.3.4. matrix determinant
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.4.0. (determinant-lu a)
|
(packages/libnum/linalgebra.lsh) |
return the determinant of square matrix a
, computed using LU decomposition.
8.0.0.3.4.1. (determinant-lu-complex a)
|
(packages/libnum/linalgebra.lsh) |
return the determinant of square complex matrix a
, computed using LU decomposition.
8.0.0.3.4.2. (log-determinant-lu a)
|
(packages/libnum/linalgebra.lsh) |
return the log of the determinant of square matrix
a , computed using LU decomposition.
8.0.0.3.4.3. (log-determinant-lu-complex a)
|
(packages/libnum/linalgebra.lsh) |
return the log of the determinant of square complex matrix
a , computed using LU decomposition.
8.0.0.3.4.4. (sign-determinant-lu a)
|
(packages/libnum/linalgebra.lsh) |
return the sign of the determinant of square matrix
a , computed using LU decomposition.
8.0.0.3.4.5. (sign-determinant-lu-complex a)
|
(packages/libnum/linalgebra.lsh) |
return the log of the determinant of square complex matrix
a , computed using LU decomposition.
8.0.0.3.5. low-level functions
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.5.0. eigenvalues, eigenvectors
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.5.0.0. (eigen-symm-inplace m eigenval)
|
(packages/libnum/linalgebra.lsh) |
Compute eigenvalues of symmetric real matrix m
. The eigenvalues sorted in descending order are written in
eigenval . The content of the input matrix is destroyed.
8.0.0.3.5.0.1. (eigen-symmv-inplace m eigenvec eigenval)
|
(packages/libnum/linalgebra.lsh) |
Compute eigenvectors and eigenvalues of symmetric matrix
m . The eigenvectors are written into
eigenvec (each column is an eigenvector). The eigenvalues are
written into eigenval . Eigenvalues
and eigenvectors are sorted in descending order. The content of the
lower triangle of m is destroyed in
the process.
8.0.0.3.5.0.2. (eigen-herm-inplace m eigenvec eigenval)
|
(packages/libnum/linalgebra.lsh) |
Compute eigenvalues of Hermitian complex matrix m
(NxNx2 matrix). Vector of sorted eigenvalues is returned. The content of
the input matrix m is destroyed.
8.0.0.3.5.0.3. (eigen-hermv-inplace m eigenvec eigenval)
|
(packages/libnum/linalgebra.lsh) |
Compute eigenvalues and eigenvectors of Hermitian complex matrix
m . The eigenvalues and eigenvectors are sorted in descending
order. The content of the input matrix m
is destroyed. Each column of eigenvec
is an eigenvector. m and
eigenvec must be idx3 of doubles (idx2 of complex), and
eigenval and idx1 of doubles.
8.0.0.3.5.1. matrix decompositions
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.5.1.0. (svd-inplace A V S)
|
(packages/libnum/linalgebra.lsh) |
[from the GSL manual]: This function factorizes the M-by-N matrix A into
the singular value decomposition A = U S V^T. On output the matrix A is
replaced by U. The diagonal elements of the singular value matrix S are
stored in the vector S. The singular values are non-negative and form a
non-increasing sequence from S_1 to S_N. The matrix V contains the
elements of V in untransposed form. To form the product U S V^T it is
necessary to take the transpose of V. This routine uses the
Golub-Reinsch SVD algorithm. Content of matrix A
is destroyed in the process. Example:
(setq a [[1 2][3 4][5 6]])
(setq v (double-matrix 2 2))
(setq s (double-matrix 2))
(svd-inplace a v s)
8.0.0.3.5.1.1. (lu-decomp-inplace a p signum)
|
(packages/libnum/linalgebra.lsh) |
Compute LU decomposition of real square matrix a
, put result in a , and permutation in
p , which must an idx1 of int. The parity of the permutation
is written in signum , which must be
an idx0 of int.
8.0.0.3.5.1.2. (lu-decomp-complex-inplace a p signum)
|
(packages/libnum/linalgebra.lsh) |
Compute LU decomposition of real square matrix a
, put result in a , and permutation in
p , which must an idx1 of int. The parity of the permutation
is written in signum , which must be
an idx0 of int.
8.0.0.3.5.1.3. (cholesky-decomp-inplace a)
|
(packages/libnum/linalgebra.lsh) |
computes the Cholesky decomposition of symmetrix positive definite
matrix a into the product of diagonal
matrices: a = L L' . The cholesky
decomposition is sometimes called the square root of a matrix. On output
L is placed in the lower triangle of a
and L' in the upper triangle.
8.0.0.3.5.2. solution of linear systems.
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.5.2.0. (solve-sv-inplace a b x)
|
(packages/libnum/linalgebra.lsh) |
[adapted from the GSL manual]: This function solves the linear system
A*x=b using singular value decomposition. the result vector is written
in x . Matrix a
is destroyed in the process. Only non-zero singular values are used in
computing the solution. The parts of the solution corresponding to
singular values of zero are ignored. Matrix a
must have more columns than rows (the over-determined least-square
solution case is not implemented by the current version of GSL). The
error code of the GSL function
gsl_linalg_SV_solve is returned.
8.0.0.3.5.2.1. (solve-hh-inplace a b)
|
(packages/libnum/linalgebra.lsh) |
This function solves the system A x = b in-place using Householder
transformations. On input b should
contain the right-hand side, which is replaced by the solution on
output. The matrix a is destroyed by
the Householder transformations. Example:
(setq a [[1 2][3 4]])
= [[ 1.00 2.00 ]
[ 3.00 4.00 ]]
? (setq b [4 4])
= [ 4.00 4.00 ]
? (solve-hh a b)
= 0
? b
= [-4.00 4.00 ]
8.0.0.3.5.2.2. (solve-lu-inplace a b)
|
(packages/libnum/linalgebra.lsh) |
This function solves the system A*x=b using LU decomposition. the result
is put in b on output. Matrix
a is also destroyed in the process.
8.0.0.3.5.2.3. (solve-lu-complex-inplace a b)
|
(packages/libnum/linalgebra.lsh) |
This function solves the complex system A*x=b using LU decomposition.
the result is put in b on output.
Matrix a is also destroyed in the
process.
8.0.0.3.5.2.4. matrix inverse
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.5.2.5. (inverse-lu-inplace a i)
|
(packages/libnum/linalgebra.lsh) |
This function computes the inverse of a matrix a
using LU decomposition, storing the result in the matrix
i . The inverse is computed by solving the system A*x=b for
each column of the identity matrix. It is preferable to avoid direct
computation of the inverse whenever possible.
8.0.0.3.5.2.6. (inverse-lu-complex-inplace a i)
|
(packages/libnum/linalgebra.lsh) |
This function computes the inverse of a matrix a
using LU decomposition, storing the result in the matrix
i . The inverse is computed by solving the system A*x=b for
each column of the identity matrix. It is preferable to avoid direct
computation of the inverse whenever possible.
8.0.0.3.5.2.7. matrix determinant
|
(packages/libnum/linalgebra.lsh) |
8.0.0.3.5.2.7.0. (determinant-lu-inplace a)
|
(packages/libnum/linalgebra.lsh) |
compute the determinant of a matrix a
using LU decomposition. Matrix a is
destroyed in the process.
8.0.0.3.5.2.7.1. (determinant-lu-complex-inplace a)
|
(packages/libnum/linalgebra.lsh) |
compute the determinant of a matrix a
using LU decomposition. Matrix a is
destroyed in the process.
8.0.0.3.5.2.7.2. (log-determinant-lu-inplace a)
|
(packages/libnum/linalgebra.lsh) |
compute the log of the absolute value of the determinant of real matrix
a using LU decomposition. This function should be used when
the regular determinant function would cause an overflow or underflow.
Matrix a is destroyed in the process.
8.0.0.3.5.2.7.3. (log-determinant-lu-complex-inplace a)
|
(packages/libnum/linalgebra.lsh) |
compute the log of the absolute value of the determinant of real matrix
a using LU decomposition. This function should be used when
the regular determinant function would cause an overflow or underflow.
Matrix a is destroyed in the process.
8.0.0.3.5.2.7.4. (sign-determinant-lu-inplace a)
|
(packages/libnum/linalgebra.lsh) |
compute the log of the absolute value of the determinant of real matrix
a using LU decomposition. This function should be used when
the regular determinant function would cause an overflow or underflow.
Matrix a is destroyed in the process.
8.0.0.3.5.2.7.5. (sign-determinant-lu-complex-inplace a)
|
(packages/libnum/linalgebra.lsh) |
compute the log of the absolute value of the determinant of real matrix
a using LU decomposition. This function should be used when
the regular determinant function would cause an overflow or underflow.
Matrix a is destroyed in the process.
8.0.0.3.6. interfacing other GSL linear algebra functions to Lush
|
(packages/libnum/linalgebra.lsh) |
A simple set of macros is provided to allow calling GSL functions that
manipulate vectors and matrices from Lush. GSL accesses vectors and
matrice data through a set of access structures that are similar to
Lush's IDX but slightly different. Before calling a GSL function from
Lush, one must create these structures. Here is a simple example of how
to call GSL's linear system solver using householder decomposition:
(de solve-hh-inplace (a b)
((-idx2- (-double-)) a)
((-idx1- (-double-)) b)
(let ((ret 0))
((-int-) ret)
#{{ gsl_matrix ga;
gsl_vector gb;
IDX2GSL_MATRIX($a,ga,double);
IDX2GSL_VECTOR($b,gb,double);
$ret = gsl_linalg_HH_svx(&ga,&gb);
}#} ret))
The macros IDX2GSL_MATRIX and
IDX2GSL_VECTOR take a Lush IDX and fill up a corresponding
gsl_matrix and gsl_vector
respectively. The GSL function gsl_linalg_HH_svx
can then be called. There is no need for a back-conversion to IDX since
only the data is manipulated by the call, and not the access structures.
8.0.0.3.6.0. IDX2GSL_VECTOR(idx1,gslvector,type)
|
(packages/libnum/linalgebra.lsh) |
a C macro that converts a Lush IDX structure idx1
describing a vector (an idx1) into a GSL vector (a
gsl_vector structure). type
is the numerical type (e.g. float, double, int...). example:
IDX2GSL_VECTOR($b,gb,double);
8.0.0.3.6.1. IDX2GSL_MATRIX(idx2,gslmatrix,type)
|
(packages/libnum/linalgebra.lsh) |
a C macro that converts a Lush IDX structure idx2
describing a matrix (an idx2) into a GSL matrix (a
gsl_matrix structure). type
is the numerical type (e.g. float, double, int...). example:
IDX2GSL_MATRIX($a,ga,double);
8.0.0.3.6.2. IDX2GSL_VECTOR_COMPLEX(idx2,gslvectorcomplex,type)
|
(packages/libnum/linalgebra.lsh) |
a C macro that converts a Lush IDX structure idx2
describing a vector of complex (an idx2 whose 2nd dimension is 2) into a
GSL vector of complex (a gsl_vector_complex
structure). type is the numerical type
(float or double). example:
IDX2GSL_VECTOR_COMPLEX($b,gb,double);
8.0.0.3.6.3. IDX2GSL_MATRIX_COMPLEX(idx3,gslmatrixcomplex,type)
|
(packages/libnum/linalgebra.lsh) |
a C macro that converts a Lush IDX structure idx3
describing a matrix (an idx3 whose last dimension is 2) into a GSL
complex matrix (a gsl_matrix_complex
structure). type is the numerical type
(float or double). example:
IDX2GSL_MATRIX_COMPLEX($a,ga,double);
8.0.0.3.6.4. IDX2GSL_PERMUTATION(idx1,gslpermutation)
|
(packages/libnum/linalgebra.lsh) |
a C macro that converts a Lush IDX structure idx1
describing a vector of integers into a GSL permutation (a
gsl_permutation structure). example:
IDX2GSL_PERMUTATION($b,gb);