IAM

OPENSOURCEFAN STUDYING
STUDYINGCOMPUTERSCIENCEANDMATH COMPUTERSCIENCE

Check out the latest superpixel benchmark — Superpixel Benchmark (2016) — and let me know your opinion! @david_stutz

ARTICLE

Matrix Decompositions Demonstrated in PHP

This article presents an application demonstrating common used matrix decompositions and their applications implemented in PHP.

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 application

The 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)$

What is your opinion on this article? Did you find it interesting or useful? Let me know your thoughts in the comments below or using the following platforms:

@david_stutz  

  • Vicky Budhiraja

    I have this mat:

    1 -0.7 0.5 -0.4
    -0.7 1 -0.5 0.5
    0.5 -0.5 1 -0.6
    -0.4 0.5 -0.6 1

    I compare the Cholesky() results with MATLAB and this lib, the results seems different. Or am I missing something?

    Any suggestions?

    – Vicky

    • davidstutz

      You have to distinguish between the classical Cholesky decomposition and the LDL (or for real matrices, the LDLT) variant of the cholesky decomposition. As described in “Numerik für Ingeneure und Naturwissenschaftler”, W. Dahmen, A. Reusken, Springer (sorry that I have to refer to german literature), the algorithm implemented in my demonstration application is the LDL variant of the Cholesky decomposition.

      In Matlab you get the classical Cholesky decomposition by using chol(A) and the LDL variant by using ldl(A) where A is your input matrix. Given your example matrix, I get the same results both in MatLab and my demonstration application.

      Here are the links to the MatLab documentation of both versions:
      http://www.mathworks.de/de/help/matlab/ref/chol.html
      http://www.mathworks.de/de/help/matlab/ref/ldl.html