Up | Prev | PrevTail | Tail |
A very powerful feature of REDUCE is the ease with which matrix calculations can be performed. This package extends the available matrix feature to enable calculations with sparse matrices. This package also provides a selection of functions that are useful in the world of linear algebra with respect to sparse matrices.
The package is loaded by: load_package sparse;
To extend the the syntax to this class of calculations we need to add an expression type sparse.
An identifier may be declared a sparse variable by the declaration SPARSE. The size of the sparse matrix must be declared explicitly in the matrix declaration. For example,
declares AA to be a 10 x 1 (column) sparse matrix and Y to be a 200 x 200 sparse matrix. The declaration SPARSE is similar to the declaration MATRIX. Once a symbol is declared to name a sparse matrix, it can not also be used to name an array, operator, procedure, or used as an ordinary variable. For more information see the Matrix Variables section in The REDUCE User’s Manual[2].
Once a matix has been declared a sparse matrix all elements of the matrix are initialized to 0. Thus when a sparse matrix is initially referred to the message
is returned. When printing out a matrix only the non-zero elements are printed. This is due to the fact that only the non-zero elements of the matrix are stored. To assign the elements of the declared matrix we use the following syntax. Assuming AA and BB have been declared as spasre matrices, we simply write,
etc. This then sets the element in the first row and first column to 10, or the element in the 100th row and 150th column to a.
Once an element of a sparse matrix has been assingned, it may be referred to in standard array element notation. Thus aa(2,1) refers to the element in the second row and first column of the sparse matrix AA.
These follow the normal rules of matrix algebra. Sums and products must be of compatible size; otherwise an error will result during evaluation. Similarly, only square matrices may be raised to a power. A negative power is computed as the inverse of the matrix raised to the corresponding positive power. For more information and the syntax for matrix algebra see the Matrix Expressions section in The REDUCE User’s Manual[2].
The operators in the Sparse Matix Package are the same as those in the Matrix Packge with the exception that the NULLSPACE operator is not defined. See section Operators with Matrix Arguments in The REDUCE User’s Manual[2] for more details.
In the examples the matrix will be
=
This package is an extension of the Linear Algebra Package for REDUCE.[1] These functions are described alphabetically in section 6 of this document and are labelled 6.1 to 6.47. They can be classified into four sections(n.b: the numbers after the dots signify the function label in section 6).
spadd_columns | … | 6.1 | spadd_rows | … | 6.2 |
spadd_to_columns | … | 6.3 | spadd_to_rows | … | 6.4 |
spaugment_columns | … | 6.5 | spchar_poly | … | 6.9 |
spcol_dim | … | 6.12 | spcopy_into | … | 6.14 |
spdiagonal | … | 6.15 | spextend | … | 6.16 |
spfind_companion | … | 6.17 | spget_columns | … | 6.18 |
spget_rows | … | 6.19 | sphermitian_tp | … | 6.21 |
spmatrix_augment | … | 6.27 | spmatrix_stack | … | 6.29 |
spminor | … | 6.30 | spmult_columns | … | 6.31 |
spmult_rows | … | 6.32 | sppivot | … | 6.33 |
spremove_columns | … | 6.35 | spremove_rows | … | 6.36 |
sprow_dim | … | 6.37 | sprows_pivot | … | 6.38 |
spstack_rows | … | 6.41 | spsub_matrix | … | 6.42 |
spswap_columns | … | 6.44 | spswap_entries | … | 6.45 |
spswap_rows | … | 6.46 |
Functions that create sparse matrices.
spband_matrix | … | 6. 6 | spblock_matrix | … | 6. 7 |
spchar_matrix | … | 6. 8 | spcoeff_matrix | … | 6. 11 |
spcompanion | … | 6. 13 | sphessian | … | 6. 22 |
spjacobian | … | 6. 23 | spjordan_block | … | 6. 24 |
spmake_identity | … | 6. 26 |
spchar_poly | … | 6.9 | spcholesky | … | 6.10 |
spgram_schmidt | … | 6.20 | splu_decom | … | 6.25 |
sppseudo_inverse | … | 6.34 | svd | … | 6.43 |
matrixp | … | 6.28 | sparsematp | … | 6.39 |
squarep | … | 6.40 | symmetricp | … | 6.47 |
In the examples the matrix will be
=
Unfortunately, due to restrictions of size, it is not practical to use “large” sparse matrices in the examples. As a result the examples shown may appear trivial, but they give an idea of how the functions work.
Throughout is used to indicate the identity matrix and
T to indicate the
transpose of the matrix
.
spadd_columns(,c1,c2,expr);
![]() | :- | a sparse matrix. |
c1,c2 | :- | positive integers. |
expr | :- | a scalar expression. |
Synopsis:
spadd_columns replaces column c2 of by expr ∗ column(
,c1)
+ column(
,c2).
spadd_rows performs the equivalent task on the rows of .
Examples:
spadd_columns( ![]() | = | ![]() |
spadd_rows( ![]() | = | ![]() |
Related functions:
spadd_to_columns, spadd_to_rows, spmult_columns, spmult_rows.
see: spadd_columns.
spadd_to_columns(,column_list,expr);
![]() | :- | a sparse matrix. |
column_list | :- | a positive integer or a list of positive integers. |
expr | :- | a scalar expression. |
Synopsis:
spadd_to_columns adds expr to each column specified in column_list of
.
spadd_to_rows performs the equivalent task on the rows of .
Examples:
spadd_to_columns( ![]() | = | ![]() |
spadd_to_rows( ![]() | = | ![]() |
Related functions:
spadd_columns, spadd_rows, spmult_rows, spmult_columns.
see: spadd_to_columns.
spaugment_columns(,column_list);
![]() | :- | a sparse matrix. |
column_list | :- | either a positive integer or a list of positive integers. |
Synopsis:
spaugment_columns gets hold of the columns of specified in
column_list and sticks them together.
spstack_rows performs the same task on rows of .
Examples:
spaugment_columns( ![]() | = | ![]() |
spstack_rows( ![]() | = | ![]() |
Related functions:
spget_columns, spget_rows, spsub_matrix.
spband_matrix(expr_list,square_size);
expr_list | :- | either a single scalar expression or a list of an odd number of scalar expressions. |
square_size | :- | a positive integer. |
Synopsis:
spband_matrix creates a sparse square matrix of dimension square_size.
Examples:
spband_matrix({x,y,z}, 6) | = | ![]() |
Related functions:
spdiagonal.
spblock_matrix(r,c,matrix_list);
r,c | :- | positive integers. |
matrix_list | :- | a list of matrices of either sparse or matrix type. |
Synopsis:
spblock_matrix creates a sparse matrix that consists of r by c matrices filled from the matrix_list row wise.
Examples:
![]() ![]() | ![]() ![]() | ![]() ![]() |
spblock_matrix(2, 3,{ ![]() ![]() ![]() ![]() ![]() ![]() | = | ![]() |
spchar_matrix(,λ);
![]() | :- | a square sparse matrix. |
λ | :- | a symbol or algebraic expression. |
Synopsis:
spchar_matrix creates the characteristic matrix of
.
This is = λ ∗
−
.
Examples:
spchar_matrix( ![]() | = | ![]() |
Related functions:
spchar_poly.
spchar_poly(,λ);
![]() | :- | a sparse square matrix. |
λ | :- | a symbol or algebraic expression. |
Synopsis:
spchar_poly finds the characteristic polynomial of .
This is the determinant of λ ∗−
.
Examples:
spchar_poly(,x) = x3 − 15 ∗ x2 − 59 ∗ x − 45
Related functions:
spchar_matrix.
spcholesky();
![]() | :- | a positive definite sparse matrix containing numeric entries. |
Synopsis:
spcholesky computes the cholesky decomposition of .
It returns {,
} where
is a lower matrix,
is an upper matrix,
=
, and
=
T .
Examples:
=
cholesky( ![]() | = | ![]() |
Related functions:
splu_decom.
spcoeff_matrix({lin_eqn1,lin_eqn2, …,lin_eqnn});
lin_eqn1,lin_eqn2, …,lin_eqnn | :- | linear equations. Can be of the form equation = number or just equation. |
Synopsis:
spcoeff_matrix creates the coefficient matrix of the linear
equations.
It returns {,
,
} such that
=
.
Examples:
spcoeff_matrix({y−20∗w = 10,y−z = 20,y +4+3∗z,w +x+50}) =
column_dim();
![]() | :- | a sparse matrix. |
Synopsis:
spcol_dim finds the column dimension of .
sprow_dim finds the row dimension of .
Examples:
spcol_dim() = 3
spcompanion(poly,x);
poly | :- | a monic univariate polynomial in x. |
x | :- | the variable. |
Synopsis:
spcompanion creates the companion matrix of poly.
This is the square matrix of dimension n, where n is the degree of poly w.r.t. x.
The entries of are:
(i,n) = -coeffn(poly,x,i-1) for i = 1 …n,
(i,i-1) = 1 for i
= 2 …n and the rest are 0.
Examples:
spcompanion(x4 + 17 ∗ x3 − 9 ∗ x2 + 11,x) | = | ![]() |
Related functions:
spfind_companion.
spcopy_into(,
,r,c);
![]() ![]() | :- | matrices of type sparse or matrix. |
r,c | :- | positive integers. |
Synopsis:
spcopy_into copies matrix into
with
(1,1) at
(r,c).
Examples:
=
spcopy_into( ![]() ![]() | = | ![]() |
Related functions:
spaugment_columns, spextend, spmatrix_augment, spmatrix_stack, spstack_rows, spsub_matrix.
spdiagonal({mat1,mat2, …,matn});29
mat1,mat2, …,matn | :- | each can be either a scalar expr or a square matrix of sparse or matrix type. |
Synopsis:
spdiagonal creates a sparse matrix that contains the input on the diagonal.
Examples:
=
spdiagonal({ ![]() ![]() | = | ![]() |
Related functions:
spjordan_block.
spextend(,r,c,expr);
![]() | :- | a sparse matrix. |
r,c | :- | positive integers. |
expr | :- | algebraic expression or symbol. |
Synopsis:
spextend returns a copy of that has been extended by r rows and c
columns. The new entries are made equal to expr.
Examples:
spextend( ![]() | = | ![]() |
Related functions:
spcopy_into, spmatrix_augment, spmatrix_stack, spremove_columns, spremove_rows.
spfind_companion(,x);
![]() | :- | a sparse matrix. |
x | :- | the variable. |
Synopsis:
Given a sparse companion matrix, spfind_companion finds the polynomial from which it was made.
Examples:
=
spfind_companion(,x) = x4 + 17 ∗ x3 − 9 ∗ x2 + 11
Related functions:
spcompanion.
spget_columns(,column_list);
![]() | :- | a sparse matrix. |
c | :- | either a positive integer or a list of positive integers. |
Synopsis:
spget_columns removes the columns of specified in column_list and
returns them as a list of column matrices.
spget_rows performs the same task on the rows of .
Examples:
spget_columns( ![]() | = | ![]() |
spget_rows( ![]() | = | ![]() |
Related functions:
spaugment_columns, spstack_rows, spsub_matrix.
see: spget_columns.
spgram_schmidt({vec1,vec2, …,vecn});
vec1,vec2, …,vecn | :- | linearly independent vectors. Each vector must be written as a list of predefined sparse (column) matrices, eg: sparse a(4,1);, a(1,1):=1; |
Synopsis:
spgram_schmidt performs the gram_schmidt orthonormalisation on the input vectors.
It returns a list of orthogonal normalised vectors.
Examples:
Suppose a,b,c,d correspond to sparse matrices representing the following lists:- {{1,0,0,0},{1,1,0,0},{1,1,1,0},{1,1,1,1}}.
spgram_schmidt({{a},{b},{c},{d}}) = {{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}}
sphermitian_tp();
![]() | :- | a sparse matrix. |
Synopsis:
sphermitian_tp computes the hermitian transpose of .
Examples:
=
sphermitian_tp( ![]() | = | ![]() |
Related functions:
tp30 .
sphessian(expr,variable_list);
expr | :- | a scalar expression. |
variable_list | :- | either a single variable or a list of variables. |
Synopsis:
sphessian computes the hessian matrix of expr w.r.t. the variables in variable_list.
Examples:
sphessian(x ∗ y ∗ z + x2,{w,x,y,z}) | = | ![]() |
spjacobian(expr_list,variable_list);
expr_list | :- | either a single algebraic expression or a list of algebraic expressions. |
variable_list | :- | either a single variable or a list of variables. |
Synopsis:
spjacobian computes the jacobian matrix of expr_list w.r.t. variable_list.
Examples:
spjacobian({x4,x ∗ y2,x ∗ y ∗ z3},{w,x,y,z}) =
Related functions:
sphessian, df31 .
spjordan_block(expr,square_size);
expr | :- | an algebraic expression or symbol. |
square_size | :- | a positive integer. |
Synopsis:
spjordan_block computes the square jordan block matrix of
dimension square_size.
Examples:
spjordan_block(x,5) | = | ![]() |
Related functions:
spdiagonal, spcompanion.
splu_decom();
![]() | :- | a sparse matrix containing either numeric entries or imaginary entries with numeric coefficients. |
Synopsis:
splu_decom performs LU decomposition on , ie: it returns {
,
}
where
is a lower diagonal matrix,
an upper diagonal matrix and
=
.
caution:
The algorithm used can swap the rows of during the calculation. This
means that
does not equal
but a row equivalent of it. Due to this,
splu_decom returns {
,
,vec}. The call spconvert(
,vec)
will return the sparse matrix that has been decomposed, ie:
=
spconvert(
,vec).
Examples:
=
lu := splu_decom( ![]() | = | ![]() |
first lu * second lu | = | ![]() |
convert( ![]() | = | ![]() |
Related functions:
spcholesky.
spmake_identity(square_size);
square_size | :- | a positive integer. |
Synopsis:
spmake_identity creates the identity matrix of dimension square_size.
Examples:
spmake_identity(4) | = | ![]() |
Related functions:
spdiagonal.
spmatrix_augment({mat1,mat2, …,matn});32
mat1,mat2, …,matn | :- | matrices. |
Synopsis:
spmatrix_augment joins the matrices in matrix_list together horizontally.
spmatrix_stack joins the matrices in matrix_list together vertically.
Examples:
spmatrix_augment({ ![]() ![]() | = | ![]() |
spmatrix_stack({ ![]() ![]() | = | ![]() |
Related functions:
spaugment_columns, spstack_rows, spsub_matrix.
matrixp(test_input);
test_input | :- | anything you like. |
Synopsis:
matrixp is a boolean function that returns t if the input is a matrix of type sparse or matrix and nil otherwise.
Examples:
matrixp() = t
matrixp(doodlesackbanana) = nil
Related functions:
squarep, symmetricp, sparsematp.
see: spmatrix_augment.
spminor(,r,c);
![]() | :- | a sparse matrix. |
r,c | :- | positive integers. |
Synopsis:
spminor computes the (r,c)’th minor of .
Examples:
spminor( ![]() | = | ![]() |
Related functions:
spremove_columns, spremove_rows.
spmult_columns(,column_list,expr);
![]() | :- | a sparse matrix. |
column_list | :- | a positive integer or a list of positive integers. |
expr | :- | an algebraic expression. |
Synopsis:
spmult_columns returns a copy of in which the columns specified in
column_list have been multiplied by expr.
spmult_rows performs the same task on the rows of .
Examples:
spmult_columns( ![]() | = | ![]() |
spmult_rows( ![]() | = | ![]() |
Related functions:
spadd_to_columns, spadd_to_rows.