The solution of linear algebra problems lies at the heart of many of the CCP and HEC codes. For example, equations of motion generally require the solution of coupled linear systems of equations. Here we summarise some classes of linear algebra and provide information on where to look to find suitable libraries and softwarefor solving these problems.

Across the broad spectrum of CCP and HEC codes, solutions are needed for:

• Linear systems:
  • Solve a set of coupled linear systems of equations
  • The equivalent matrix problem AX=B, where A is a matrix with n rows and n columns, and both B and X have n rows and m columns, A and B are known and wish to compute the entries in X
  • Sparse problems:
    • Typically, each equation only couples together a small number of the unknown variables => most rows in A consist of only a small number of non-zero values
    • This “sparsity” can be taken advantage of in the solution process
    • Sparse Direct Factorization Methods
      • Factor A into matrices that are easy to solve with and use the factorization to solve AX=B. For example, A=LDU, where L is a lower triangular, D is a diagonal matrix and U is upper triangular
      • Pros: Can reuse the factorization and some methods allow for minor updates to A
      • Cons: Problem size or nature of problem (e.g. 3D discretizations) can make sparse direct factorization methods prohibitive
    • (Preconditioned) Iterative Methods
      • Perform iterative procedure to converge to solution X
      • Normally need to be able to efficiently multiply a vector with the matrix A
      • Pros: Typically, uses less memory than sparse direct factorization; knowledge of properties of A can help choose best suited iterative method
      • Cons: Properties of A can result in slow convergence and a preconditioner is needed to accelerate convergence
  • Structured problems:
    • The underlying matrix has a structure that can be exploited in the solution phase via either a direct factorization, iterative or hybrid (mix of direct factorization and iterative) method
  • Dense or non-sparse/non-structured linear systems
    • Typically, each equation couples a large number of unknown variables
    • The equivalent matrix problem AX=B, where A and B are known, is such that little or no advantage can be made with respect to the existence of entries in A that are zero
    • In general, the size of matrix problem that can be solved is much smaller than the sparse matrix counterparts.
• Eigenvalue and eigenvector problems
  • Given matrices square matrices A and B with n rows/columns, solve w_iAv_i=Bv_i, where w_i is a real or complex value (known as an eigenvalue) and v_i is a vector of length n (known as an eigenvector). Wide range of problems types: some need just a few eigenvalues; some need all the eigenvalues and eigenvectors; and some lie in the middle of these two extremes
  • Sparse problems:
    • Both A and B are sparse matrices (small number of non-zero entries)
    • This “sparsity” can be taken advantage of in the solution process
  • Structured problems:
    • Both A and B have a form that can be taken advantage of in the solution phase
  • Dense or non-sparse/non-structured problems
    • Neither A or B have structures or sparsity that can be exploited in the solution phase

Available Software

There are a large number of libraries and routines available and they should be investigated before attempting to implement your own version of known methods. Jack Dongarra’s Software for Linear Algebra page lists open source and free to academics libraries/routines and their properties.