5.Appendix

Compressed Column Storage format

qpSWIFT operates on sparse matrices which are stored in Compressed Column Storage (CCS) format. In this format, an m x n sparse matrix A that contains nnz non-zero entries is stored as an integer array Ajc of length n+1, an integer array Air of length nnz, and a real array Apc of length nnz.

• The real array Apr holds all the nonzero entries of A in column-major format
• The integer array Air holds the indices of the rows of the corresponding elements in Apr
• The integer array Ajc is defined as
  • Ajc[0] = 0
  • Ajc[i] = Ajc[i − 1] + number of non-zeros in ith column of A

Example

For the following sample matrix A,

we have the following CCS representation

Permutation vector

Directly performing factorization on a sparse matrix A typically results in fill-in. A fill-in is a non-zero entry in L but not in A. The higher the fill-in, the higher is the memory required to store the matrix factors (L and D) as well as the associated floating-point operations. To minimize fill-in, permutation matrices are used and the new system

is factorized. Obtaining a perfect elimination ordering (permutation matrix with least fill-in) is an NP-hard problem. Hence, heuristics are used to compute permutation matrices. Some of the popular ones are nested dissection and minimum degree ordering methods. qpSWIFT uses the Approximate Minimum Degree (AMD) ordering to compute permutation matrix. The user can opt to use other ordering methods as well by passing the argument Permut in each of the interfaces.