File SparseAssembly.h

↰ Parent directory (ADS/numeric)

The assembly of a sparse matrix from its triplets, beyond the book: the entries ( i , j , v ) in any order, with repetitions, become the arrays of the compressed form that the solvers of linear programs take (beg, ind and val, by columns or by rows), written in the arrays of the caller, with no matrix object in between and no other allocation than a workspace that a caller may keep from one assembly to the next.

Definition (ADS/numeric/SparseAssembly.h)

Detailed Description

compressTriplets() first distributes the entries by their major index (the column of the compressed sparse columns, the row of the compressed sparse rows), by the counting sort [Knuth, section 5.2]: one read of the major indices counts them, the prefix sums give beg, and a second read of the triplets writes each entry at the cursor of its major index in ind and val, straight into the arrays of the caller, so that each major index has its entries in the order of the input. Then each major index sums its repetitions and sorts its distinct entries: a mark per minor index, the place written last for it plus 1, tells whether a minor index already has a place in the current major index (the places of the earlier ones all come before it), and if so the value is added there, in the order of the input, otherwise it takes the next place [Davis, chapter 2]; the distinct entries are then sorted by their minor indices, by insertion up to 32 of them, i.e., at most :math:` k ( k - 1 ) / 2 ` moves for k of them and none if they are already in order, and by the sort of the library beyond. Only one pass scatters the entries over memory, where the sort by the least significant index first, or the transposition of a matrix built by the other index (as in setFromTriplets() of Eigen), scatters them twice; the time is :math:` O( z + m + n + sum_i min( k_i^2 , k_i log k_i ) ) ` for z triplets of an :math:` m times n ` matrix whose major index i has :math:` k_i ` distinct entries, i.e., :math:` O( z + m + n ) ` for rows or columns of bounded length, and the workspace holds a cursor per major index, a mark per minor one and the pairs of the longest major index past 32 entries.

assembleCsc() and assembleCsr() name the two orientations: beg has one entry more than the major indices, beg[ k ] being the first entry of the major index k and beg[ last ] the number of the entries, ind the minor index of each entry and val its value. The entries summed to 0 stay, as the solvers accept them.

The contracts [see File Contract.h]: the indices of the triplets are below the dimensions, beg has room for the major indices plus 1, ind and val for the triplets, and the number of the triplets fits the index type I. The functions are defined in SparseAssembly.tpp.

    1. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, 2nd ed., Addison-Wesley, 1998, section 5.2 (the distribution counting, and the sort by the least significant digit first)

    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

    1. Davis, Direct Methods for Sparse Linear Systems, SIAM, 2006, doi:10.1137/1.9780898718881, chapter 2 (the compression of the triplets and the sum of the duplicates)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions