SPARSE: Sparse Matrix Calculations

REDUCE

20.52 SPARSE: Sparse Matrix Calculations

Author: Stephen Scowcroft

20.52.1 Introduction

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.

Loading the Package

The package is loaded by: load_package sparse;

20.52.2 Sparse Matrix Calculations

To extend the the syntax to this class of calculations we need to add an expression type sparse.

20.52.2.1 Sparse Variables

An identiﬁer 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,

sparse aa(10,1),bb(200,200);

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 (14.2).

20.52.2.2 Assigning Sparse Matrix Elements

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

"Empty matrix"

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,

aa(1,1):=10;
bb(100,150):=a;

etc. This then sets the element in the ﬁrst row and ﬁrst column to 10, or the element in the 100th row and 150th column to a.

20.52.2.3 Evaluating Sparse Matrix Elements

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 ﬁrst column of the sparse matrix aa.

20.52.3 Sparse Matrix Expressions

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 (14.3).

20.52.4 Operators with Sparse Matrix Arguments

The operators in the Sparse Matrix Package are the same as those in the Matrix Package with the exception that the nullspace operator is not deﬁned. See section Operators with Matrix Arguments (14.4) for more details.

20.52.4.1 Examples

In the examples the matrix 𝒜𝒜 will be

$( 1 0 0 0 ) | 0 3 0 0 | 𝒜 𝒜 = |( |) 0 0 5 0 0 0 0 9$

det aa;

135

trace aa;

18

rank aa;

4

spmateigen(aa,eta);

{{eta - 1,1,

  spm(1,1) := arbcomplex(1)$
  },

 {eta - 3,1,

  spm(2,1) := arbcomplex(2)$
  },

 {eta - 5,1,

  spm(3,1) := arbcomplex(3)$
  },

 {eta - 9,1,

  spm(4,1) := arbcomplex(4)$
  }}

20.52.5 The Linear Algebra Package for Sparse Matrices

This package is an extension of the Linear Algebra Package for REDUCE described in section 20.32. These functions are described alphabetically in section 20.52.6. They can be classiﬁed into four sections(n.b: the numbers after the dots signify the function label in section 6).

20.52.5.1 Basic matrix handling

spadd_columns	…	20.52.6.1	spadd_rows	…	20.52.6.2
spadd_to_columns	…	20.52.6.3	spadd_to_rows	…	20.52.6.4
spaugment_columns	…	20.52.6.5	spchar_poly	…	20.52.6.9
spcol_dim	…	20.52.6.12	spcopy_into	…	20.52.6.14
spdiagonal	…	20.52.6.15	spextend	…	20.52.6.16
spﬁnd_companion	…	20.52.6.17	spget_columns	…	20.52.6.18
spget_rows	…	20.52.6.19	sphermitian_tp	…	20.52.6.21
spmatrix_augment	…	20.52.6.27	spmatrix_stack	…	20.52.6.29
spminor	…	20.52.6.30	spmult_columns	…	20.52.6.31
spmult_rows	…	20.52.6.32	sppivot	…	20.52.6.33
spremove_columns	…	20.52.6.35	spremove_rows	…	20.52.6.36
sprow_dim	…	20.52.6.37	sprows_pivot	…	20.52.6.38
spstack_rows	…	20.52.6.41	spsub_matrix	…	20.52.6.42
spswap_columns	…	20.52.6.44	spswap_entries	…	20.52.6.45
spswap_rows	…	20.52.6.46

20.52.5.2 Constructors

Functions that create sparse matrices.

spband_matrix	…	20.52.6.6	spblock_matrix	…	20.52.6.7
spchar_matrix	…	20.52.6.11	spcoeﬀ_matrix	…	20.52.6.11
spcompanion	…	20.52.6.13	sphessian	…	20.52.6.22
spjacobian	…	20.52.6.23	spjordan_block	…	20.52.6.24
spmake_identity	…	20.52.6.26

20.52.5.3 High level algorithms

spchar_poly	…	20.52.6.9	spcholesky	…	20.52.6.10
spgram_schmidt	…	20.52.6.20	splu_decom	…	20.52.6.25
sppseudo_inverse	…	20.52.6.34	spsvd	…	20.52.6.43

20.52.5.4 Predicates

matrixp	…	20.52.6.28	sparsematp	…	20.52.6.39
squarep	…	20.52.6.40	symmetricp	…	20.52.6.47

Note on examples:

In the examples the matrix 𝒜 will be

$( ) 1 0 0 𝒜 = ( 0 5 0) 0 0 9$

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.

Notation

Throughout ℐ is used to indicate the identity matrix and 𝒜^T to indicate the transpose of the matrix 𝒜.

20.52.6 Available Functions

20.52.6.1 spadd_columns, spadd_rows

Syntax:

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).
add_rows performs the equivalent task on the rows of 𝒜.

Examples:

spadd_columns $( ) 1 x 0 (𝒜,1,2,x) = ( 0 5 0) 0 0 9$
spadd_rows $( ) 1 0 0 (𝒜, 2,3,5) = ( 0 5 0) 0 25 9$

Related functions:

spadd_to_columns, spadd_to_rows, spmult_columns, spmult_rows.

20.52.6.2 spadd_rows

See: spadd_columns.

20.52.6.3 spadd_to_columns, spadd_to_rows

Syntax:

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 speciﬁed in column_list of 𝒜.

spadd_to_rows performs the equivalent task on the rows of 𝒜.

Examples:

spadd_to_columns $( ) 11 10 0 (𝒜, {1,2},10) = (10 15 0) 10 10 9$
spadd_to_rows $( ) 1 0 0 (𝒜, 2,− x) = ( − x − x + 5 − x) 0 0 9$

Related functions:

spadd_columns, spadd_rows, spmult_rows, spmult_columns.

20.52.6.4 spadd_to_rows

See: spadd_to_columns.

20.52.6.5 spaugment_columns, spstack_rows

Syntax:

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 𝒜 speciﬁed in column_list and sticks them together.

spstack_rows performs the same task on rows of 𝒜.

Examples:

spaugment_columns $( ) 1 0 (𝒜,{1,2}) = ( 0 5) 0 0$
spstack_rows $(1 0 0) (𝒜,{1,3} ) = 0 0 9$

Related functions:

spget_columns, spget_rows, spsub_matrix.

20.52.6.6 spband_matrix

Syntax:

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 $( ) y z 0 0 0 0 || x y z 0 0 0|| | 0 x y z 0 0| ({x,y,z},6) = || 0 0 x y z 0|| |( 0 0 0 x y z|) 0 0 0 0 x y$

Related functions:

spdiagonal.

20.52.6.7 spblock_matrix

Syntax:

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 ﬁlled from the matrix_list row wise.

Examples:

$( ) ( ) ( ) 1 0 5 22 0 ℬ = 0 1 , 𝒞 = 0 , 𝒟 = 0 0$
spblock_matrix $( 1 0 5 22 0) | | (2,3,{ℬ, 𝒞,𝒟,𝒟, 𝒞,ℬ }) = |( 0 1 0 0 0|) 22 0 5 1 0 0 0 0 0 1$

20.52.6.8 spchar_matrix

Syntax:

spchar_matrix(𝒜,λ);

𝒜	:-	a square sparse matrix.
λ	:-	a symbol or algebraic expression.

Synopsis:

spchar_matrix creates the characteristic matrix 𝒞 of 𝒜.

This is 𝒞 = λ ∗ℐ−𝒜.

Examples:

spchar_matrix $( ) x− 1 0 0 (𝒜,x) = ( 0 x − 5 0 ) 0 0 x − 9$

Related functions:

spchar_poly.

20.52.6.9 spchar_poly

Syntax:

spchar_poly(𝒜,λ);

𝒜	:-	a sparse square matrix.
λ	:-	a symbol or algebraic expression.

Synopsis:

spchar_poly ﬁnds the characteristic polynomial of 𝒜.

This is the determinant of λ ∗ℐ−𝒜.

Examples:

spchar_poly(𝒜,x) = x³ − 15 ∗x² − 59 ∗x − 45

Related functions:

spchar_matrix.

20.52.6.10 spcholesky

Syntax:

spcholesky(𝒜);

𝒜

a positive deﬁnite 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:

$( 1 0 0) ( ) ℱ = 0 5 0 0 0 9$
cholesky $( ( ) ( ) ) { 1 √0- 0 1 √0-- 0 } (ℱ ) = ( 0 5 0) ,(0 5 0) ( 0 0 3 0 0 3 )$

Related functions:

splu_decom.

20.52.6.11 spcoeﬀ_matrix

Syntax:

spcoeff_matrix({lin_eqn₁,lin_eqn₂, …,lin_eqn_n});

lin_eqn₁,lin_eqn₂, …,lin_eqn_n

linear equations. Can be of the form equation = number or just equation which is equivalent to equation = 0.

Synopsis:

spcoeff_matrix creates the coeﬃcient 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 }) =$
$( ( ) ( ) ( ) ) ||{ | 1 − 20 0 0| | y| | 10| ||} | 1 0 − 1 0| ,| w| ,| 20| ||( ( 1 0 3 0) ( z) ( − 4) ||) 0 1 0 1 x 50$

20.52.6.12 spcol_dim, sprow_dim

Syntax:

column_dim(𝒜);

𝒜

a sparse matrix.

Synopsis:

spcol_dim ﬁnds the column dimension of 𝒜.
sprow_dim ﬁnds the row dimension of 𝒜.

Examples:

spcol_dim(𝒜) = 3

20.52.6.13 spcompanion

Syntax:

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 $( ) 0 0 0 − 11 (x4 + 17∗ x3 − 9 ∗x2 + 11,x) = || 1 0 0 0 || ( 0 1 0 9 ) 0 0 1 − 17$

Related functions:

spfind_companion.

20.52.6.14 spcopy_into

Syntax:

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:

$(0 0 0 0) |0 0 0 0| 𝒢 = |( |) 0 0 0 0 0 0 0 0$
spcopy_into $( ) 0 1 0 0 || 0 0 5 0|| (𝒜,𝒢,1,2) = ( 0 0 0 9) 0 0 0 0$

Related functions:

spaugment_columns, spextend, spmatrix_augment, spmatrix_stack, spstack_rows, spsub_matrix.

20.52.6.15 spdiagonal

Syntax:

spdiagonal({mat₁,mat₂, …,mat_n});⁴⁵

mat₁,mat₂, …,mat_n

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:

$( ) 66 77 ℋ = 88 99$
spdiagonal $( 1 0 0 0 0 0) | 0 5 0 0 0 0| || || ({𝒜, x,ℋ }) = || 0 0 9 0 0 0|| | 0 0 0 x 0 0| ( 0 0 0 0 66 77) 0 0 0 0 88 99$

Related functions:

spjordan_block.

20.52.6.16 spextend

Syntax:

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 $( ) 1 0 0 0 0 | 0 5 0 0 0| (𝒜, 1,2,0) = |( 0 0 9 0 0|) 0 0 0 0 0$

Related functions:

spcopy_into, spmatrix_augment, spmatrix_stack, spremove_columns, spremove_rows.

20.52.6.17 spﬁnd_companion

Syntax:

spfind_companion(𝒜,x);

𝒜	:-	a sparse matrix.
x	:-	the variable.

Synopsis:

Given a sparse companion matrix, spfind_companion ﬁnds the polynomial from which it was made.

Examples:

$( 0 0 0 − 11) | 1 0 0 0 | 𝒞 = |( |) 0 1 0 9 0 0 1 − 17$
spfind_companion $(𝒞,x) = x4 + 17 ∗x3 − 9 ∗x2 + 11$

Related functions:

spcompanion.

20.52.6.18 spget_columns, spget_rows

Syntax:

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 𝒜 speciﬁed 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 $( ) { ( 1) (0 )} (𝒜,{1,3}) = ( 0) ,(0 ) ( 0 9 )$
spget_rows ${( )} (𝒜, 2) = 0 5 0$

Related functions:

spaugment_columns, spstack_rows, spsub_matrix.

20.52.6.19 spget_rows

See: spget_columns.

20.52.6.20 spgram_schmidt

Syntax:

spgram_schmidt({vec₁,vec₂, …,vec_n});

vec₁,vec₂, …,vec_n

linearly independent vectors. Each vector must be written as a list of predeﬁned 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}}

20.52.6.21 sphermitian_tp

Syntax:

sphermitian_tp(𝒜);

𝒜

a sparse matrix.

Synopsis:

sphermitian_tp computes the hermitian transpose of 𝒜.

Examples:

$( ) i+ 1 i+ 2 i+ 3 𝒥 = ( 0 0 0 ) 0 i 0$
sphermitian_tp $( − i+ 1 0 0 ) (𝒥 ) = ( − i+ 2 0 − i) − i+ 3 0 0$

Related functions:

tp⁴⁶ .

20.52.6.22 sphessian

Syntax:

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 $(0 0 0 0) |0 2 z y| (x ∗ y ∗ z + x2,{w, x,y,z}) = |( |) 0 z 0 x 0 y x 0$

20.52.6.23 spjacobian

Syntax:

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}) =$
$( ) 0 4∗ x3 0 0 ( 0 y2 2∗ x∗ y 0 ) 0 y ∗ z3 x ∗z3 3∗ x ∗y ∗z2$

Related functions:

sphessian, df⁴⁷ .

20.52.6.24 spjordan_block

Syntax:

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) $( x 1 0 0 0) | 0 x 1 0 0| || || = |( 0 0 x 1 0|) 0 0 0 x 1 0 0 0 0 x$

Related functions:

spdiagonal, spcompanion.

20.52.6.25 splu_decom

Syntax:

splu_decom(𝒜);

𝒜

a sparse matrix containing either numeric entries or imaginary entries with numeric coeﬃcients.

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:

$( ) 1 0 0 𝒦 = ( 0 5 0) 0 0 9$

lu := splu_decom $( ( ) ( ) ) { 1 0 0 1 0 0 } (𝒦) = (0 5 0) ,(0 1 0) ,[ 1 2 3 ] ( 0 0 9 0 0 1 )$

$( ) 1 0 0 first lu * second lu = ( 0 5 0) 0 0 9$
$( ) 1 0 0 convert (𝒦,third lu ) = ( 0 5 0) 0 0 9$

Related functions:

spcholesky.

20.52.6.26 spmake_identity

Syntax:

spmake_identity(square_size);

square_size

a positive integer.

Synopsis:

spmake_identity creates the identity matrix of dimension square_size.

Examples:

spmake_identity $( ) 1 0 0 0 (4) = || 0 1 0 0|| ( 0 0 1 0) 0 0 0 1$

Related functions:

spdiagonal.

20.52.6.27 spmatrix_augment, spmatrix_stack

Syntax:

spmatrix_augment({mat₁,mat₂, …,mat_n});⁴⁸

mat₁,mat₂, …,mat_n

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 $( ) 1 0 0 1 0 0 ({𝒜, 𝒜 }) = ( 0 5 0 0 5 0) 0 0 9 0 0 9$
spmatrix_stack $( 1 0 0) | | || 0 5 0|| ({𝒜, 𝒜 }) = | 0 0 9| || 1 0 0|| ( 0 5 0) 0 0 9$

Related functions:

spaugment_columns, spstack_rows, spsub_matrix.

20.52.6.28 matrixp

Syntax:

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.

20.52.6.29 spmatrix_stack

See: spmatrix_augment.

20.52.6.30 spminor

Syntax:

spminor(𝒜,r,c);

𝒜	:-	a sparse matrix.
r,c	:-	positive integers.

Synopsis:

spminor computes the (r,c)’th minor of 𝒜.

Examples:

spminor $( ) (𝒜, 1,3) = 0 5 0 0$

Related functions:

spremove_columns, spremove_rows.

20.52.6.31 spmult_columns, spmult_rows

Syntax:

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 speciﬁed in column_list have been multiplied by expr.

spmult_rows performs the same task on the rows of 𝒜.

Examples:

spmult_columns $( x 0 0 ) (𝒜,{1,3},x ) = ( 0 5 0 ) 0 0 9 ∗x$
spmult_rows $( ) 1 0 0 (𝒜,2,10) = ( 0 50 0) 0 0 9$

Related functions:

spadd_to_columns, spadd_to_rows.

20.52.6.32 spmult_rows

See: spmult_columns.

20.52.6.33 sppivot

Syntax:

sppivot(𝒜,r,c);

𝒜	:-	a sparse matrix.
r,c	:-	positive integers such that 𝒜(r,c) neq 0.

Synopsis:

sppivot pivots 𝒜 about it’s (r,c)’th entry.

To do this, multiples of the r’th row are added to every other row in the matrix.

This means that the c’th column will be 0 except for the (r,c)’th entry.

Related functions:

sprows_pivot.

20.52.6.34 sppseudo_inverse

Syntax:

sppseudo_inverse(𝒜);

𝒜

a sparse matrix containing only real numeric entries.

Synopsis:

sppseudo_inverse, also known as the Moore-Penrose inverse, computes the pseudo inverse of 𝒜.

Given the singular value decomposition of 𝒜, i.e: 𝒜 = 𝒰Σ𝒱^T, then the pseudo inverse 𝒜^† is deﬁned by 𝒜^† = 𝒱Σ^†𝒰^T. For the diagonal matrix Σ, the pseudoinverse Σ^† is computed by taking the reciprocal of only the nonzero diagonal elements.

If 𝒜 is square and non-singular, then 𝒜^† = 𝒜. In general, however, 𝒜𝒜^†𝒜 = 𝒜, and 𝒜^†𝒜𝒜^† = 𝒜^†.

Perhaps more importantly, 𝒜^† solves the following least-squares problem: given a rectangular matrix 𝒜 and a vector b, ﬁnd the x minimizing ∥𝒜x −b∥₂, and which, in addition, has minimum ℓ₂ (euclidean) Norm, ∥x∥₂. This x is 𝒜^†b.

Examples:

$( ) ℛ = 0 0 3 0 9 0 7 0$
sppseudo_inverse $( − 0.26 0.11 ) | 0 0 | (ℛ ) = |( 0.33 0 |) 0.25 − 0.05$

Related functions:

spsvd.

20.52.6.35 spremove_columns, spremove_rows

Syntax:

spremove_columns(𝒜,column_list);

𝒜	:-	a sparse matrix.
column_list	:-	either a positive integer or a list of positive integers.

Synopsis:

spremove_columns removes the columns speciﬁed in column_list from 𝒜.

spremove_rows performs the same task on the rows of 𝒜.

Examples:

spremove_columns $(1 0) (𝒜, 2) = (0 0) 0 9$
spremove_rows $( ) (𝒜, {1,3}) = 0 5 0$

Related functions:

spminor.

20.52.6.36 spremove_rows

See: spremove_columns.

20.52.6.37 sprow_dim

See: spcolumn_dim.

20.52.6.38 sprows_pivot

Syntax:

sprows_pivot(𝒜,r,c,{row_list});

𝒜	:-	a sparse matrix.
r,c	:-	positive integers such that 𝒜(r,c) neq 0.
row_list	:-	positive integer or a list of positive integers.

Synopsis:

sprows_pivot performs the same task as sppivot but applies the pivot only to the rows speciﬁed in row_list.

Related functions:

sppivot.

20.52.6.39 sparsematp

Syntax:

sparsematp(𝒜);

𝒜

a matrix.

Synopsis:

sparsematp is a boolean function that returns t if the matrix is declared sparse and nil otherwise.

Examples:

$ℒ := mat ((1,2,3 ),(4,5,6 ),(7,8,9 ));$
sparsematp $(𝒜 ) = t$
sparsematp $(ℒ ) = nil$

Related functions:

matrixp, symmetricp, squarep.

20.52.6.40 squarep

Syntax:

squarep(𝒜);

𝒜

a matrix.

Synopsis:

squarep is a boolean function that returns t if the matrix is square and nil otherwise.

Examples:

$( ) ℒ = 1 3 5$
squarep $(𝒜) = t$
squarep $(ℒ) = nil$

Related functions:

matrixp, symmetricp, sparsematp.

20.52.6.41 spstack_rows

See: spaugment_columns.

20.52.6.42 spsub_matrix

Syntax:

spsub_matrix(𝒜,row_list,column_list);

𝒜	:-	a sparse matrix.
row_list, column_list	:-	either a positive integer or a list of positive integers.

Synopsis:

spsub_matrix produces the matrix consisting of the intersection of the rows speciﬁed in row_list and the columns speciﬁed in column_list.

Examples:

spsub_matrix $( ) (𝒜, {1,3},{2,3}) = 5 0 0 9$

Related functions:

spaugment_columns, spstack_rows.

20.52.6.43 spsvd (singular value decomposition)

Syntax:

spsvd(𝒜);

𝒜

a sparse matrix containing only real numeric entries.

Synopsis:

spsvd computes the singular value decomposition of 𝒜.

If A is an m ×n real matrix of (column) rank r, svd returns the 3-element list {𝒰,Σ,𝒱} where 𝒜 = 𝒰Σ𝒱^T.

Let k = min(m,n). Then U is m ×k, V is n ×k, and and Σ = diag(σ₁,…,σ_k), where σ_i ≥ 0 are the singular values of 𝒜; only r of these are non-zero. The singular values are the non-negative square roots of the eigenvalues of 𝒜^T𝒜.

𝒰 and 𝒱 are such that 𝒰𝒰^T = 𝒱𝒱^T = 𝒱^T𝒱 = ℐ_k.

Note: there are a number of diﬀerent deﬁnitions of SVD in the literature, in some of which Σ is square and U and V rectangular, as here, but in others U and V are square, and Σ is rectangular.

Examples:

$( ) 𝒬 = 1 0 0 3$
${ ( ) ( ) ( ) } svd(𝒬 ) = − 1 0 , 1.0 0 , − 1 0 0 0 0 5.0 0 − 1$

20.52.6.44 spswap_columns, spswap_rows

Syntax:

spswap_columns(𝒜,c1,c2);

𝒜	:-	a sparse matrix.
c1,c1	:-	positive integers.

Synopsis:

spswap_columns swaps column c1 of 𝒜 with column c2.

spswap_rows performs the same task on 2 rows of 𝒜.

Examples:

spswap_columns $( ) 1 0 0 (𝒜,2,3) = ( 0 0 5) 0 9 0$

Related functions:

spswap_entries.

20.52.6.45 swap_entries

Syntax:

spswap_entries(𝒜,{r1,c1},{r2,c2});

𝒜	:-	a sparse matrix.
r1,c1,r2,c2	:-	positive integers.

Synopsis:

spswap_entries swaps 𝒜(r1,c1) with 𝒜(r2,c2).

Examples:

spswap_entries $( ) 9 0 0 (𝒜,{1,1},{3,3} ) = ( 0 5 0) 0 0 1$

Related functions:

spswap_columns, spswap_rows.

20.52.6.46 spswap_rows

See: spswap_columns.

20.52.6.47 symmetricp

Syntax:

symmetricp(𝒜);

𝒜

a matrix.

Synopsis:

symmetricp is a boolean function that returns t if the matrix is symmetric and nil otherwise.

Examples:

$( ) 1 2 ℳ = 2 1$
symmetricp $(𝒜 ) = nil$
symmetricp $(ℳ ) = t$

Related functions:

matrixp, squarep, sparsematp.

20.52.7 Fast Linear Algebra

By turning the fast_la switch on, the speed of the following functions will be increased:

spadd_columns	spadd_rows	spaugment_columns	spcol_dim
spcopy_into	spmake_identity	spmatrix_augment	spmatrix_stack
spminor	spmult_column	spmult_row	sppivot
spremove_columns	spremove_rows	sprows_pivot	squarep
spstack_rows	spsub_matrix	spswap_columns	spswap_entries
spswap_rows	symmetricp

The increase in speed will be insigniﬁcant unless you are making a signiﬁcant number(i.e: thousands) of calls. When using this switch, error checking is minimised. This means that illegal input may give strange error messages. Beware.

20.52.8 Acknowledgments

This package is an extention of the code from the Linear Algebra Package for REDUCE by Matt Rebbeck (cf. section 20.32).

The algorithms for spcholesky, splu_decom, and spsvd are taken from the book Linear Algebra – J.H. Wilkinson & C. Reinsch[3].

The spgram_schmidt code comes from Karin Gatermann’s Symmetry package[4] for REDUCE.

PrevTail

Front