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.