LU decomposition in PHP

I have released NumPHP 1.0.0-dev3. With this release I have added the LU decomposition. Now you can factor every matrix in a lower and a upper triangular matrix. And a permutation matrix.

An Example

We have Matrix A:

| 1 , 6 , 1 |
| 2 , 3 , 2 |
| 4 , 2 , 1 |

Create Matrix A

$matrixA = new NumArray(
    [
        [1, 6, 1],
        [2, 3, 2],
        [4, 2, 1],
    ]
);

Call LUDecomposition

list($matrixP, $matrixL, $matrixU) = \NumPHP\LinAlg\LinAlg::lud($matrixA);

Solution

The complete example can be found under NumPHP-examples as Symfony Command. The command has the following output

Matrix A:
NumArray([
  [1, 6, 1],
  [2, 3, 2],
  [4, 2, 1]
])
LU decomposition
Matrix P:
NumArray([
  [0, 1, 0],
  [0, 0, 1],
  [1, 0, 0]
])
Matrix L:
NumArray([
  [1, 0, 0],
  [0.25, 1, 0],
  [0.5, 0.36363636363636, 1]
])
Matrix U:
NumArray([
  [4, 2, 1],
  [0, 5.5, 0.75],
  [0, 0, 1.2272727272727]
])
Time for calculation: 0.0027289390563965 sec

Testing the solution with Numpy

Numpy is always my reference. Here is a small Numpy script to proof my solution.

import time
import numpy
from scipy.linalg import lu

A = numpy.array([[1., 6., 1.], [2., 3., 2.], [4., 2., 1.]])

time1 = time.time()
P, L, U = lu(A)
timeDiff = time.time()-time1

print("P")
print(P)
print("L")
print(L)
print("U")
print(U)
print "%.16f" % timeDiff

And here the output of this script:

P
[[ 0.  1.  0.]
 [ 0.  0.  1.]
 [ 1.  0.  0.]]
L
[[ 1.          0.          0.        ]
 [ 0.25        1.          0.        ]
 [ 0.5         0.36363636  1.        ]]
U
[[ 4.          2.          1.        ]
 [ 0.          5.5         0.75      ]
 [ 0.          0.          1.22727273]]
0.0000779628753662

I'm pretty happy, that my result is the same. But NumPHP is damm slow.

Determinant of a Matrix

As a cool side effect, you can now calculate the determinant of an matrix in PHP. Cause the Determinant is the product of the entries of the main diagonal of the U matrix.

// will output 27.0
echo \NumPHP\LinAlg\LinAlg::det($aMatrix);