# OptimQR

## 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:
**optimqr** The main optimizer program
**codegen.pl** A Fortran-77 code generator
- Various small utilities

# 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:
- Get and compile the
**OptimQR** package.
- Write your system description in a file.
- Run
**optimqr** on that description.
- Run
**codegen.pl** on the output from **optimqr**.
- Now, you have an efficient solver in the file
**fastqr.f**
which you can use with your Fortran program that needs the system solved.

# 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 ?

## Acknowledgements

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.

## License

The software is distributed under the GNU Public License.

## Download

Get the tarball here: download.