cholesky decomposition floating point error

Question

Implementing the Choleky decomposition in Python without the use of numpy.linalg.* (yes this is an assignment) I encountered a Problem regarding the use of floating point numbers. My Algorithm works fine with regualar integers:

    for i in range(n):
        for k in range(i + 1):
            sum = 0
            for j in range(k):
                sum += L[i, j] * L[k, j]
            if i == k:
                if M[i, i] - sum < 0:
                    raise ValueError("Matrix is non-positive definite")
                L[i, i] = np.sqrt(M[i, i] - sum)
            else:
                if np.isclose(L[k, k] * (M[i, k] - sum), 0):
                    raise ValueError("Matrix is non-positive definite")
                L[i, k] = (L[k, k] * (M[i, k] - sum)) ** (-1)

I tested the matrix for symmetry beforehand; n is the dimension and L becomes the lower triangular Cholesky Factor.

Using random floating point nxn matrices multiplied with their transpose (in order to get a positive definite matrix) both ValueErrors are raised, i.e w/out raising the ValueErrors the L output matrix is partly filled with NaN and inf values. How can I work with floating point numbers in python?

Edit: Minimal Reproducible Example:

M = np.random.randn(2, 2)
M = np.dot(M, M.transpose())
# produces for example [[0.68283219, -0.33497034], [-0.33497034, 0.72113541]]
run_cholesky(M)

score 1 · Accepted Answer · answered Dec 15 '19 at 12:47

Saving M[i, k] in a variable and then subtracting instead of summing up is fixing the problem:

for i in range(n):
    for k in range(i + 1):
        val = M[i, k]
        for j in range(k):
            val -= L[i, j] * L[k, j]
        if i == k:
            if val < 0:
                raise ValueError("Matrix is non-positive definite")
            L[i, k] = np.sqrt(val)
        else:
            if np.isclose(L[k, k], 0):
                raise ValueError("Matrix is non-positive definite")
            L[i, k] = val / L[k, k]

score 0 · Answer 2 · answered Dec 14 '19 at 22:44

0

Declare the matrix like this , and go from there :

M = np.zeros((n, n), dtype=float)

answered Dec 14 '19 at 22:44

KevinWendellCrumb

157
2
10

cholesky decomposition floating point error

2 Answers2