1
$\begingroup$

I wrote this code to find Cholesky factorization of a symmetric positive definite matrix in MatLab:

function L = cholesky(A)
    n = length(A);
    L = zeros(n, n);
    for i=1:n
        l = L_solver(L(1:i-1, 1:i-1), A(1:i-1, i));
        L(i, 1:i-1) = l;
        L(i, i) = sqrt(A(i, i) - l.'*l);
    end
end

Which L_solver(L, b) solves linear system $Lx=b$ and returns $x$. Then I tried to improve it. If the input matrix $A$ is not positive definite, it finds the least non-negative integer $t$ such if we add $tI$ to $A$, it becomes positive definite and we can return its Cholesky factorization. And we also return that $t$. This is how I modified the code:

function [L, t] = cholesky_decomposition(A)
    n = length(A);
    t = 0;
    while true
        L = zeros(n, n);
        found = true;
        for i=1:n
            l = L_solver(L(1:i-1, 1:i-1), A(1:i-1, i));
            L(i, 1:i-1) = l;
            L(i, i) = sqrt(A(i, i) - l.'*l);
            if (imag(L(i, i)) > 0) || A(i, i) <= 0
                t = t + 1;
                A = A + eye(n, n);
                found = false;
                break;
            end
        end
        if found
            break;
        end
    end
end

As I searched, the most efficient method to check if a matrix is positive definite, is to check if it has Cholesky factorization. So I try to factorize it and if I reach an entry on the main diagonal that isn't positive or inside the square-root becomes negative, I add $I$ to the matrix. I want to know if these two conditions are correct and enough in this scenario.

$\endgroup$
1
  • 2
    $\begingroup$ Just a small nitpick (but a professionally important one), while enough is a decent word to describe what you want to ask, it is still vague. Mathematically precise terms are "sufficient conditions" and "necessary conditions". $\endgroup$ Nov 13, 2023 at 20:39

1 Answer 1

5
$\begingroup$

You are trying to figure out what is known as Modified Cholesky. There are a lot of resources on it, but McSweeney's thesis is a good starting point "Modified Cholesky Decomposition and Applications". This thesis builds upon a lot of prior work, particularly, "Sheung Hun Cheng and Nicholas Higham, A Modified Cholesky Algorithm Based on a Symmetric Indefinite Factorization, SIAM J. Matrix Anal. Appl. 19(4), 1097–1110, 1998."

There is a related GitHub repository with Matlab code in it: https://github.com/higham/modified-cholesky

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.