Example of sparse storage, LU factors and solution
Storage
Consider the storage vectors
Note, non-zeros are not stored
The matrix is
Build linked lists
Printed twice to display all entries
Index of First entry in this row in Value Table
Location of next entry in row
Location of next entry in column
Index of First entry in this column in Value Table
Finding Entries
Find
Row 2
From Fir Starts at element
From Ncol
From NIR Next element in row
From Ncol
From NIR Next element in row
From Ncol
Find
Row 4
Starts at element
4
Next element in row
Next element in row
Next element in row
NO ENTRY FOR A41!!!!!!
Alternate Schemes
In the above example we really did not use Fic, Nic, and Nrow. We could however have organized our search by column instead. In general only Fir, Ncol and Nir OR Fic, Nic and Nrow are needed.
Within these it is often useful to group by row or column in scending orderin Value, Nir, Nic
Modifying storage
If a matrix entry changes from zero to non zero we must add storage
Factorization
Concept of Fillin's
Refer to Eq. 2.25-2.26 Fillin's occur in LU factorization whenever
and Akj=0
and Ajk=0
Determining potential fillins is called symbolic factorization
Factoring Column 1 does not produce fillins
Factoring Row 1 does not produce fillins
Factoring column 2
Locate A12
Look at Column 1
Diagonal element
Element A21 changes
Element A51 changes
A52 new NZ
done with column
Fillins require extending the Value NIC NIR Nrow and Ncol vectors. This is done dynamically. I will just add four more cells to each
To accomodate the fill in A52, let it occupy the 16 th position in Value. Modify Nrow and Ncol
accordingly
NIC and NIR will also change
Column 2 has a new entry.
Column 2 starts at
Follow the links to Col 2 elements
Make NIC7 point to fillin
Continue in this manner till done
So with fill in sparse storage looks like this
Finding LU decomposition
Lu factors will be stored right back in Value
Column 1 does not change
Row 1
Diagonal element
Element 1 2
Element 1 5
Column 2
It is easier to follow col1 and row 1 as we update col 2
store this diagonal
same element
Element 1 2 is NZ; will affect col 2
Go down col 1
Elements 1,2 and 2,1 will combine to affect q 22
Find the location of q 22
This implements equation q22=a22-q21q12 on page 90
Elements 1,2 and 5,1 will combine to affect q 52
Find the loca