Matrix decompositions are used in numerical analysis to solve a wide range of problems. Throuhgout a course of numerical analysis at university I found myself implementing some of the corresponding algorithms in PHP - which is a very unusual programming language for numerical purposes. I decided to put them together to form a small application demonstrating some common matrix decompositions and their usage. The project can be found on GitHub.
GitHub projectDemonstration applicationThe following table gives an overview of the decompositions covered:
Decomposition | Factorization | Applicable for | Runtime |
---|---|---|---|
LU | $A = LU$ | $A \in \mathbb{R}^{n \times n}$, $A$ regular | $\mathcal{O}(\frac{1}{3}n^3)$ |
Cholesky | $A = LDL^T$ | $A \in \mathbb{R}^{n \times n}$, $A$ symmetric and positive definite | $\mathcal{O}(\frac{1}{6}n^3)$ |
QR: Givens Rotations | $A = QR$ | $A \in \mathbb{R}^{m \times n}$ | $\mathcal{O}(\frac{4}{3}n^3)$ |
QR: Householder Transformations | $A = QR$ | $A \in \mathbb{R}^{m \times n}$ | $\mathcal{O}(\frac{2}{3}n^3)$ |