A Software-package to create near-optimal solvers for sparse systems of linear equations

What is it ?

OptimQR is a package consisting of several programs:

What can it do ?

The optimqr program will read a description of the sparsity pattern of some system matrix for system of linear equations. It will then apply heuristic branch&bound search to find a near-optimal ordering of the rows and columns of the system matrix. The ordering is written to disk.

The codegen.pl program can then read the system ordering, and create a solver written in Fortran-77, that will solve the system using sparse QR factorization (using Givens rotations).

For what is it good ?

Usually, the QR factorization is considered ``expensive'' compared to LU and other factorizations. However, the QR factorization is orthogonal, so, if we have a solver that can solve a system of some given structure (sparsity pattern), that solver can solve all systems obeying that structure. The solver will not need to reconsider row-ordering, in order to solve systems with other numeric values of the elements either in the system matrix or in the right-hand-side.

So, if you need to solve a sparse system of linear equations repeatedly, and the system maintains the same sparsity pattern, then you are likely to see much better performance from the generated QR solver, than from eg. a LU solver.

How do I use it then ?

The steps are simple, and described in the User's Guide. But in short, these are the steps involved:

How does it work ?

A description of the entire project can be found in the report Discrete Optimization of the Sparse QR Factorization, using Heuristic Branch&Bound Search.

How fast is it ?

A short benchmark is available here

How do I get the software ?


This software was developed for UNI-C, and I was given credit for the work at The Department for Mathematical Modelling at The Technical University of Denmark.


The software is distributed under the GNU Public License.


Get the tarball here: download.