Saturday 18 June 2011

Matrix processing

  • Exponentiating by squaring. Quickly computes powers of numbers and matrices.
  • Rutishauser. Algorithm for tridiagonalizing banded matrices. Uses the standard chasing step.
  • Strassen algorithm. Faster matrix multiplication.
  • Symbolic Cholesky decomposition. Efficient way of storing sparse matrix.
  • Zha's algorithm. For tridiagonalizing arrowhead matrices, improves Rutishauser.
  • Matrix chain multiplication. Given a sequence of matrices, we want to find the most efficient way to multiply these matrices together using dynamic programming (not to perform the multiplication).