File SparseMatrix.h

↰ Parent directory (ADS/numeric)

A sparse matrix on orthogonal lists, beyond the book (2.2.6 of Knuth): each nonzero entry is a node on the circular list of its row, sorted by column, and on that of its column, sorted by row, each list with a head node; the space is O( m + n + nnz ) and an entry is found by walking its row.

Definition (ADS/numeric/SparseMatrix.h)

Detailed Description

pivot() is the pivot step of Algorithm 2.2.6S, the core of the elimination by exchange: with the pivot :math:` a ` in the row r and the column c, the pivot becomes :math:` 1 / a , the rest of its row :math: b / a , the rest of its column :math: - c / a , and every other entry d with a nonzero b in its column of the pivot row and c in its row of the pivot column becomes :math: d - b c / a `, the entries that become zero leaving the lists and those that appear (the fill-in) entering them; it costs time proportional to the nonzeros it touches. A pivot step on each diagonal place, in turn, inverts a matrix whose pivots are not zero.

The contracts [see File Contract.h]: the places are in the matrix, and the pivot is not zero; the invariant is that the lists are sorted and that a node is on the lists of its row and of its column, an audit. The operations are defined in SparseMatrix.tpp.

    1. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Addison-Wesley, 1997, section 2.2.6

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes