mc64

Scalings and matchings of real sparse matrices.

Legal

The source code is distributed under the 3-Clause BSD license (LICENSE or https://opensource.org/license/bsd-3-clause).

A partial translation of Sparse Parallel Robust Algorithms Library (SPRAL) from The Science and Technology Facilities Council's (STFC) Computational Mathematics Group, based at Rutherford Appleton Laboratory.

lib.rs:

This package generates various scalings (and matchings) of real sparse matrices.

Given a symmetric matrix A, it finds a diagonal matrix D such that the scaled matrix

 Â = DAD

has specific numerical properties.

Given an unsymmetric or rectangular matrix A, it finds diagonal matrices Dr and Dc such that the scaled matrix

 Â = D_r A D_c

has specific numerical properties.

The specific numerical properties delivered depends on the algorithm used:

Matching-based algorithms scale A such that the maximum (absolute) value in each row and column of Â is exactly 1.0, where the entries of maximum value form a maximum cardinality matching. The Hungarian algorithm delivers an optimal matching slowly, whereas the auction algorithm delivers an approximate matching quickly.

Norm-equilibration algorithms scale A such that the infinity norm of each row and column of Â is 1.0 ± τ (for some user specified tolerance τ).