From 478515477f131a5b05ef0b4a067bfd215ae76731 Mon Sep 17 00:00:00 2001
From: Michael Orlitzky <michael@orlitzky.com>
Date: Mon, 28 Sep 2020 14:28:22 -0400
Subject: [PATCH] mjo/ldlt.py: add a vaguely correct non-recursive ldlt_fast().

---
 mjo/ldlt.py | 88 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 88 insertions(+)

diff --git a/mjo/ldlt.py b/mjo/ldlt.py
index 8f39198..d113df3 100644
--- a/mjo/ldlt.py
+++ b/mjo/ldlt.py
@@ -124,3 +124,91 @@ def ldlt_naive(A):
                             [0*v1,   D2]])
 
     return (P1,L1,D1)
+
+
+
+def ldlt_fast(A):
+    r"""
+    Perform a fast, pivoted `LDL^{T}` factorization of the Hermitian
+    positive-semidefinite matrix `A`.
+
+    This function is much faster than ``ldlt_naive`` because the
+    tail-recursion has been unrolled into a loop.
+    """
+    n = A.nrows()
+    ring = A.base_ring().fraction_field()
+
+    A = A.change_ring(ring)
+
+    # Don't try to store the results in the lower-left-hand corner of
+    # "A" itself; there lies madness.
+    L = copy(A.matrix_space().identity_matrix())
+    D = copy(A.matrix_space().zero())
+
+    # Keep track of the permutations in a vector rather than in a
+    # matrix, for efficiency.
+    p = list(range(n))
+
+    for k in range(n):
+        # We need to loop once for every diagonal entry in the
+        # matrix. So, as many times as it has rows/columns. At each
+        # step, we obtain the permutation needed to put things in the
+        # right place, then the "next" entry (alpha) of D, and finally
+        # another column of L.
+        diags = A.diagonal()[k:n]
+        alpha = max(diags)
+
+        # We're working *within* the matrix ``A``, so every index is
+        # offset by k. For example: after the second step, we should
+        # only be looking at the lower 3-by-3 block of a 5-by-5 matrix.
+        s = k + diags.index(alpha)
+
+        # Move the largest diagonal element up into the top-left corner
+        # of the block we're working on (the one starting from index k,k).
+        # Presumably this is faster than hitting the thing with a
+        # permutation matrix.
+        A.swap_columns(k,s)
+        A.swap_rows(k,s)
+
+        # Have to do L, too, to keep track of the "P2.T" (which is 1 x
+        # P3.T which is 1 x P4 T)... in the recursive
+        # algorithm. There, we compute P2^T from the bottom up. Here,
+        # we apply the permutations one at a time, essentially
+        # building them top-down (but just applying them instead of
+        # building them.
+        L.swap_columns(k,s)
+        L.swap_rows(k,s)
+
+        # Update the permutation "matrix" with the next swap.
+        p_k = p[k]
+        p[k] = p[s]
+        p[s] = p_k
+
+        # Now the largest diagonal is in the top-left corner of
+        # the block below and to the right of index k,k....
+        # Note: same as ``pivot``.
+        D[k,k] = alpha
+
+        # When alpha is zero, we can just leave the rest of the D/L entries
+        # zero... which is exactly how they start out.
+        if alpha != 0:
+            # Update the "next" block of A that we'll work on during
+            # the following iteration. I think it's faster to get the
+            # entries of a row than a column here?
+            v = vector(ring, A[k,k+1:n].list())
+            b = v.column()*v.row()/alpha
+            for i in range(n-k-1):
+                for j in range(i+1):
+                    # Something goes wrong if I try to access the kth row/column
+                    # of A to save the intermediate "b" here...
+                    A[k+1+i,k+1+j] = A[k+1+i,k+1+j] - b[i,j]
+                    A[k+1+j,k+1+i] = A[k+1+i,k+1+j] # keep it symmetric!
+
+            # Store the "new" (kth) column of L.
+            for i in range(n-k-1):
+                L[k+i+1,k] = v[i]/alpha
+
+    I = A.matrix_space().identity_matrix()
+    P = matrix.column( I.row(p[j]) for j in range(n) )
+
+    return P,L,D
-- 
2.44.2