Discrete Optimization of
The Sparse QR Factorization

Using Heuristic Branch & Bound search

JAKOB ØSTERGAARD
5th of October 1998






IMM - DTU¹
UNI$\bullet$C²

This project was conducted at the Institute of Mathematical Modelling, at the Technical University of Denmark, and at UNI$\bullet$C, Danish Computing Center for Research and Education, during the late spring, summer, and autumn of 1998.

The original idea behind this project, came from Claus Bendtsen, of UNI$\bullet$C. In short, he was interested in investigating whether discrete optimization of QR factorization would be beneficial, if at all possible, in relation to another project he was involved in.

During the time of the project, I have had much good advice, and some interesting and most enlightening conversations with Professor Jens Clausen, of IMM, DTU, who supervised this project.

Abstract:

When using certain mathematical models for simulating aerial pollution, it becomes interesting to be able to solve some specific system of linear equations as fast as possible. This report describes an attempt made, to optimize the performance of a solver using sparse QR factorization, and back-substitution. The optimization problem is complex, and it quickly turns out that attempting an exhaustive search thru the solution space is absurd. A branch-and-bound algorithm is developed, and using different search strategies and heuristics, solutions of varying quality are found.

I will present the methods I used for finding ``good'' solutions, as well as some of the approaches that failed. This is by no means a thorough mathematical treatment of the problem. It is a document describing a number of approaches taken, and their usefulness in actual applications.

Jakob Østergaard, October 1998, Lyngby