Repository: keon/algorithms
Pull request #552 (2019-10-13 06:57:18)

Add cholesky matrix decomposition
… its tests.

(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [X] **If creating a new file :**
  - [X] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


keon: thanks! this is an example of a good PR

Patch:
diff --git a/README.md b/README.md
index f30d452..4b67fe5 100644
--- a/README.md
+++ b/README.md
@@ -223,6 +223,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [sparse_mul](algorithms/matrix/sparse_mul.py)
     - [spiral_traversal](algorithms/matrix/spiral_traversal.py)
 	- [crout_matrix_decomposition](algorithms/matrix/crout_matrix_decomposition.py)
+	- [cholesky_matrix_decomposition](algorithms/matrix/cholesky_matrix_decomposition.py)
 - [queues](algorithms/queues)
     - [max_sliding_window](algorithms/queues/max_sliding_window.py)
     - [moving_average](algorithms/queues/moving_average.py)
diff --git a/algorithms/matrix/cholesky_matrix_decomposition.py b/algorithms/matrix/cholesky_matrix_decomposition.py
new file mode 100644
index 0000000..4b5e24e
--- /dev/null
+++ b/algorithms/matrix/cholesky_matrix_decomposition.py
@@ -0,0 +1,48 @@
+"""
+Cholesky matrix decomposition is used to find the decomposition of a Hermitian positive-definite matrix A
+into matrix V, so that V * V* = A, where V* denotes the conjugate transpose of L.
+The dimensions of the matrix A must match.
+
+This method is mainly used for numeric solution of linear equations Ax = b.
+
+example:
+Input matrix A:
+[[  4,  12, -16],
+ [ 12,  37, -43],
+ [-16, -43,  98]]
+
+Result:
+[[2.0, 0.0, 0.0],
+[6.0, 1.0, 0.0],
+[-8.0, 5.0, 3.0]]
+
+Time complexity of this algorithm is O(n^3), specifically about (n^3)/3
+
+"""
+import math
+
+
+def cholesky_decomposition(A):
+    """
+    :param A: Hermitian positive-definite matrix of type List[List[float]]
+    :return: matrix of type List[List[float]] if A can be decomposed, otherwise None
+    """
+    n = len(A)
+    for ai in A:
+        if len(ai) != n:
+            return None
+    V = [[0.0] * n for _ in range(n)]
+    for j in range(n):
+        sum_diagonal_element = 0
+        for k in range(j):
+            sum_diagonal_element = sum_diagonal_element + math.pow(V[j][k], 2)
+        sum_diagonal_element = A[j][j] - sum_diagonal_element
+        if sum_diagonal_element <= 0:
+            return None
+        V[j][j] = math.pow(sum_diagonal_element, 0.5)
+        for i in range(j+1, n):
+            sum_other_element = 0
+            for k in range(j):
+                sum_other_element += V[i][k]*V[j][k]
+            V[i][j] = (A[i][j] - sum_other_element)/V[j][j]
+    return V


Test patch:
diff --git a/tests/test_matrix.py b/tests/test_matrix.py
index 4d7e129..3522d7d 100644
--- a/tests/test_matrix.py
+++ b/tests/test_matrix.py
@@ -2,6 +2,7 @@ from algorithms.matrix import (
     bomb_enemy,
     copy_transform,
     crout_matrix_decomposition,
+    cholesky_matrix_decomposition,
     multiply,
     rotate_image,
     sparse_dot_vector,
@@ -93,6 +94,39 @@ class TestCroutMatrixDecomposition(unittest.TestCase):
                              [[2, 1, 3, 1], [4, 1, 4, 1], [6, 1, 7, 1], [8, 1, 9, 1]]))
 
 
+class TestCholeskyMatrixDecomposition(unittest.TestCase):
+    """[summary]
+    Test for the file cholesky_matrix_decomposition.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+
+    def test_cholesky_matrix_decomposition(self):
+        self.assertEqual([[2.0, 0.0, 0.0],
+                          [6.0, 1.0, 0.0],
+                          [-8.0, 5.0, 3.0]],
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[4, 12, -16], [12, 37, -43], [-16, -43, 98]]))
+
+        self.assertEqual( None,
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[4, 12, -8], [12, 4, -43], [-16, -1, 32]]))
+
+        self.assertEqual(None,
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[4, 12, -16], [12, 37, -43], [-16, -43, 98], [1, 2, 3]]))
+
+        # example taken from https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/04LinearAlgebra/cholesky/
+        self.assertEqual([[2.23606797749979, 0.0, 0.0, 0.0],
+                          [0.5366563145999494, 2.389979079406345, 0.0, 0.0],
+                          [0.13416407864998736, -0.19749126846635062, 2.818332343581848, 0.0],
+                          [-0.2683281572999747, 0.43682390737048743, 0.64657701271919, 3.052723872310221]],
+                         cholesky_matrix_decomposition.cholesky_decomposition(
+                             [[5, 1.2, 0.3, -0.6], [1.2, 6, -0.4, 0.9],
+                              [0.3, -0.4, 8, 1.7], [-0.6, 0.9, 1.7, 10]]))
+
+
 class TestMultiply(unittest.TestCase):
     """[summary]
     Test for the file multiply.py