Topic: Expressions

Online Help

High performance symmetric solvers


Calcpad also includes advanced solvers for two of the most common matrix problems – solution of linear systems of equations and finding the eigenvalues and eigenvector of a matrix:

PCG symmetric linear solver

Direct methods using Cholesky and LDLT factorizations are suitable for small to medium sized matrices. For larger matrices, the computational cost and solution time get too high for practical use because the asymptotic complexity of factorization is O(n3 ). In such cases, iterative solution methods are preferred. They are much faster than direct ones, especially if the matrix is well conditioned. One of the most popular of them is the preconditioned conjugate gradient (PCG) method. Its complexity is O(m√k), where m is the number of nonzero elements and k is the condition number of the matrix.

In Calcpad, the PCG method is used in the following functions:
  slsolve(A; b) - solves the symmetric linear system of equations A⃗x = ⃗b;
  smsolve(A; B) - solves the generalized symmetric matrix equation AX = B.

Since most engineering methods like FEM and finite differences use symmetric matrices, we put a lot of effort into improving this particular kind of problem. If the matrix has banded or skyline structure, the algorithm takes advantage of that by storing and processing only the elements within the bandwidth. You can achieve such structure and minimize the bandwidth by providing appropriate numbering for the joints of the FE model.

Iterative methods like PCG are approximate and the solution continues until a certain precision is achieved. In Calcpad, it is specified by setting the variable Tol. Its default value is Tol = 10-6 just like in MATLAB. If the required precision is not reached for under 1000 iterations, no convergence is assumed, so the solution is stopped with an error message. Preconditioning can often improve convergence by reducing the condition number k. In Calcpad, a simple Jacoby preconditioner is used for that purpose.

Symmetric Lanczos eigensolver

Similarly to the system of equations, the direct QL algorithm with implicit shifts we use for finding the eigenvalues and eigenvectors of matrices has a complexity of O(n3) which makes it suitable for small to medium sized problems. In addition, it always finds all eigenvalues and eigenvectors, which is not required in most cases. For example, in structural dynamics we usually need only the first of the most significant vibration frequencies and modes. The Lanczos method is much more appropriate for that purpose. It can find several of the extreme (smallest or largest) eigenvalues of a large matrix but much faster than the Implicit QL algorithm. It has a time complexity of O(k2m), where k is the number of iterations and m is the number of nonzero elements of the matrix. It is applied at the tridiagonalization step, replacing the Householder’s reflections method.

In Calcpad, it is used for the same functions as the QL method, when the size of the matrix is > 200:
  eigenvals(M; ne) - the first neeigenvalues of matrix M ;
  eigenvecs(M; ne) - the first ne eigenvectors of matrix M ;
  eigen(M; ne) - the first neeigenvalues and eigenvectors of matrix M.

The maximum number of iterations is set to be 4ne + 50. So, if the size of the matrix is n < 1000 and ne > n/5 again the QL method is used. This is because the Lanczos method is less accurate and when the number of iterations gets close to the matrix size, the performance is reduced to the one of the QL algorithm.


Table of contents