File DynamicCsr.h

↰ Parent directory (ADS/numeric)

A compressed sparse matrix that grows and shrinks by whole rows (or whole columns), beyond the book: the bundle of the cuts of a decomposition, whose rows come in batches and go away in batches, kept at all times in the arrays beg, ind and val that the solvers of linear programs take, so that handing it over costs nothing.

Definition (ADS/numeric/DynamicCsr.h)

Detailed Description

The matrix is three vectors: beg, with one entry more than the rows, beg[ i ] the first entry of the row i and beg[ last ] the number of the entries, and ind and val, the minor index and the value of each entry, the rows one after the other. append() adds a row at the end in time linear in its entries, amortized over the doubling of the vectors; remove() takes a strictly increasing set of rows and closes the gaps in one pass, moving each entry after the first row removed once, in :math:` O( r + z’ ) ` time for r rows and :math:` z’ ` entries after the first row removed, with no scratch memory. The same type is the compressed sparse columns, DynamicCsc, when the major index is a column.

The contracts [see File Contract.h]: a row has as many indices as values, the number of the entries fits the index type I, the rows removed are strictly increasing and below the number of the rows; the invariant is that beg starts at 0, never decreases and ends at the number of the entries. The operations are defined in DynamicCsr.tpp.

    1. Gustavson, Two fast algorithms for sparse matrices: multiplication and permuted transposition, ACM Transactions on Mathematical Software 4(3), 250-269, 1978, doi:10.1145/355791.355796 (the compressed sparse rows)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Typedefs