compute compressed sparse row and column forms - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Linear Algebra : LinearAlgebra Package : Solvers : LinearAlgebra/CompressedSparseForm

LinearAlgebra[CompressedSparseForm] - compute compressed sparse row and column forms

Calling Sequence

CompressedSparseForm(A, opts)

Parameters

A

-

sparse Matrix with hardware data type

opts

-

optional equations controlling the details of the computation

Description

• 

The CompressedSparseForm function computes either the compressed sparse row form or the compressed sparse column form of the input Matrix A, which needs to have one of the hardware data types. It thus performs the opposite function to FromCompressedSparseForm.

• 

The compressed sparse column form of an n by m Matrix A with k nonzero entries consists of three Vectors, CB, R, and X. These are obtained by sorting the k nonzero entries of A first by column, and then within each column sorting the entries by row. Now X is the k-element Vector of these nonzero values in A in this order, and R is the k-element Vector of row indices at which these values occur. CB is an n+1-element Vector; CBi is the index in both X and R where the ith column starts. We always have CB1=1 and CBn+1=k+1, so that the entries in column i have indices CBi up to, but not including, CBi+1. (If the cbbase option below is used, then CB1=cbbase and CBn+1=k+cbbase and a similar statement holds.)

• 

The compressed sparse row form is very similar, but with the roles of rows and columns interchanged. Specifically, we first sort A by row and then within each row by column; X is still the nonzero values occurring in A. However, R is the k-element Vector of column indices. Similarly, CBi is the index in X and R where the ith row starts.

• 

The compressed sparse forms are most useful for sparse Matrices. If A does not have sparse storage (as determined by rtable_optionX,storage being either sparse or sparseupper or sparselower), then a sparse storage copy is made before determining the compressed sparse form.

• 

If A has any indexing functions (as determined by rtable_indfnsA), then these are bypassed when determining the compressed sparse row or column form: since CompressedSparseForm is a low level command, Maple returns the compressed sparse form of the stored entries only. For example, if a Matrix is defined with option shape=symmetric and storage=sparseupper, then only one of each pair of off-diagonal entries will be represented in the compressed sparse form. However, if A has indexing functions but no sparse storage, then the copy made to give it sparse storage, as explained above, typically gets rid of the indexing function and stores all nonzero entries.

• 

The code for CompressedSparseForm relies on A being a NAG-sparse Matrix (potentially after copying it to give it sparse storage); that is, its datatype as returned by rtable_options needs to be one of these values:

  

sfloat,complexsfloat,integer1,integer2,integer4,integer8,float4,float8,complex8

Examples

withLinearAlgebra:

Let us examine the compressed sparse row and column form of an arbitrary matrix.

m:=Matrix6,6,1,2=81,2,3=55,2,4=15,3,1=46,3,3=17,3,4=99,3,5=61,4,2=18,4,5=78,5,6=22,datatype=integer4

m:=0810000005515004601799610018007800000022000000

(1)

CompressedSparseFormm

124681011,3142323345,46811855171599617822

(2)

CompressedSparseFormm,'form=row'

1248101111,2341345256,81551546179961187822

(3)

CompressedSparseFormm,'cbbase'=0

01357910,3142323345,46811855171599617822

(4)

CompressedSparseFormm,'rbase'=0

124681011,2031212234,46811855171599617822

(5)

m2:=Matrix0,1,0,2,0,0,3,0,4,5,6,7,'datatype=float'

m2:=0.1.0.2.0.0.3.0.4.5.6.7.

(6)

cb,r,x:=CompressedSparseFormm2

cb,r,x:=1468,2341434,2.3.5.1.6.4.7.

(7)

We can obtain the entries of r corresponding to the second column as follows.

column:=2

column:=2

(8)

rcbcolumn..cbcolumn+11

14

(9)

Similarly for the entries of x.

xcbcolumn..cbcolumn+11

1.6.

(10)

CompressedSparseForm does not work with Matrices that are not of a hardware data type.

m3:=Matrix3,3,i,j→ij

m3:=012101210

(11)

CompressedSparseFormm3

Error, (in LinearAlgebra:-CompressedSparseForm) cannot compute compressed sparse form of a Matrix with non-hardware datatype anything

To make this work, we need to recreate m3 with, for example, option datatype=integer4.

m3:=Matrixm3,datatype=integer4

m3:=012101210

(12)

cb,r,x:=CompressedSparseFormm3

cb,r,x:=1357,231312,121121

(13)

Here is an example of the antisymmetric indexing function being ignored.

m4:=Matrix6,datatype=integer4,shape=antisymmetric,storage=sparselower,i,j→`if`iremi+j,2=1,ij,0

m4:=010305101030010103301010030101503010

(14)

CompressedSparseFormm4

146891010,246354656,135131311

(15)

See Also

LinearAlgebra[FromCompressedSparseForm], LinearAlgebra[FromSplitForm], LinearAlgebra[SplitForm], rtable_indfns, rtable_options


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam