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