Is there a good way to check whether a matrix is positive definite?

[nanmiao wu]

Hi,

I am wondering is there a good and inexpensive way to check whether a matrix is positive definite, like we can use .isSymmetric() to check whether a matrix is symmetric.

The methods I know are:

a). check all eigenvalues.

b). check determinants of all upper-left sub-matrices are positive

But it is expensive for large matrix.

Thanks.

Best,

Nanmiao

[Klaus Iglberger]

Hi Nanmiao!

Unfortunately Blaze does not yet provide an isPositiveDefinite() function. At this point we’re also not aware of any cheaper way to check if a matrix is positive definite. However, we interpret your question as a request to add the according feature. We’ll do our best to provide such a function as soon as possible. Thanks for creating this issue,

Best regards,

Klaus!

[Mikhail Katliar]

One of the ways is to start the Cholesky decomposition algorithm on a matrix. Once you encounter a non-positive element on the diagonal from which you need to calculate the square root (part of the algorithm), you know the matrix is not positive-definite. The complexity is cubic in the size of the matrix. I am not aware of any algorithm with lower complexity.

[Mikhail Katliar]

@nanmiao wu so you can basically do potrf() or llh() on the matrix, and if it does not throw an error you know it is positive definite.

[nanmiao wu]

Hi Klaus and Mikhail,

Thanks for your help! Correct, llh() is a good and cheaper way to check. Thanks.

Best,

Nanmiao

[Klaus Iglberger]

Summary

The feature has been implemented, tested, optimized, and documented as required. It is immediately available via cloning the Blaze repository and will be officially released in Blaze 3.7.

isPositiveDefinite()

The isPositiveDefinite() function checks if the given dense matrix is positive definite.

blaze::DynamicMatrix<double> A;
// ... Initialization
if( isPositiveDefinite( A ) ) { ... }

Note that non-square matrices are never considered to be positive definite!

Note that the isPositiveDefinite() function can only be used for dense matrices with float, double, complex<float> or complex<double> element type. The attempt to call the function with matrices of any other element type or with a sparse matrix results in a compile time error!

Also note that the function is depending on LAPACK kernels. Thus the function can only be used if a fitting LAPACK library is available and linked to the executable. Otherwise a linker error will be created.