Properties from a numerical point of view

The system of linear equations

$$\mathbf{A}x=b$$

can be solved in numerous ways. However, in our specific application, we can exploit the following properties:

• $\mathbf{A}$ is sparse
• Although the elements of $\mathbf{A}$ change, the sparsity pattern of $\mathbf{A}$ is invariant.

We suggest, that QR factorization followed by simple back-substitution may be used in solving the above system, even though QR factorization is usually considered more expensive than Householder and other factorizations. The QR factorization however, is insensitive to changes in the elements in $\mathbf{A}$. This means, that if we find one good row/column ordering, and one good sequence of Givens Rotations to complete the QR factorization, that single ordering can be used for all occurring values of $\mathbf{A}$. If we used a non-orthogonal factorization, we would have to create a new factorization for every new value of $\mathbf{A}$.

The idea in this project is to use one good ordering of rows and columns, and one good sequence of Givens rotations, for all values of $\mathbf{A}$ (as long as $\mathbf{A}$ maintains the same structure). All in all, they together should minimize the computational cost of the factorization and the following back-substitution, by minimizing the number of Givens rotations needed, and minimizing the number of fill-ins produced during the factorization.