mathnet/mathnet-numerics — pull request #58 by PohlodSlavik (2012-11-20 13:56:32+00:00)
Title: Add Knuth algorithm for storage and work with sparse matrix

This algo is created by famous mathematician Donald Knuth . It differs from the common compressed row sparse storage approach with the way to store and acсess to elements. In this structure we have a node element which has a value, position in row, position in column, and two pointers: pointer to left or default element in current row and pointer to upper or default ellement in current column. We dont keep 0-elements in this structure. So we have complete structure that consists of connected elements.
Here is an example to make it easier to understand:
matrix like this:

1 0 0 0 0 2 0 0

0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
2 0 0 0 0 3 0 1
0 0 0 0 0 0 0 0
would be stored this way:
____c1 c2 c3 c4 c5 c6 c7 c8
____^___________^ _ ^__^
r1<--1 <-----------------: ---2___:
r2<---^-------------------:----^-----1
r3___:___________:__:___ ^
r4<---:-------------------1__:____:
r5<--2<----------------------3<-----1
r6
c1..c8 - default column element
r1..r8 - default row element
The other advantages of this algo is easy adding,updating, deleting, getting elements and faster realization of arifmetical oparations at matrix.
Ok, I ll try to split class into storage part and type-specific class using the example of SparseMatrix.
P.S: Sorry for my bad English, I'm just learning it)))