Eigen efficient inverse of symmetric positive definite matrix

Question

In Eigen, if we have symmetric positive definite matrix A then we can calculate the inverse of A by

A.inverse();

or

A.llt().solve(I);

where I is an identity matrix of the same size as A. But is there a more efficient way to calculate the inverse of symmetric positive definite matrix?

For example if we write the Cholesky decomposition of A as A = LL^{T}, then L^{-T} L^{-1} is an inverse of A since A L^{-T} L^{-1} = LL^{T} L^{-T} L^{-1} = I (and where L^{-T} denotes the inverse of the transpose of L).

So we could obtain the Cholesky decomposition of A, calculate its inverse, and then obtain the cross-product of that inverse to find the inverse of A. But my instinct is that calculating these explicit steps will be slower than using A.llt().solve(I) as above.

And before anybody asks, I do indeed need an explicit inverse - it is a calculation for part of a Gibbs sampler.

Tumer

While the accepted answer does not state whether there is a faster way to calculate the inverse of a symmetric positive definite matrix with Eigen, AFAIK the explicit method that I mentioned in the question is the fastest way to do it ( and has order O((1/3)n^3 + 2n^2) ) - which is apparently what Eigen does under the hood. – Tumer

Answer 1

With A.llt().solve(I), you assumes A to be a SPD matrix and apply Cholesky decomposition to solve the equation Ax=I. The mathematical procedure of solving the equation is exactly same as your explicit way. So the performance should be same if you do every step correctly.

On the other hand, with A.inverse(), you are doing general matrix inversion, which uses LU decomposition for large matrix. Thus the performance should be lower than A.llt().solve(I);.

Splashdown

Thanks this saves me a bunch of time profiling the Cholesky solve method vs. the explicit method, and at the end of the day still not knowing for sure that they are the same. – Tumer

Answer 2

You should profile the code for your specific problem to get the best answer. I was benchmarking code while trying to evaluate the viability of both approaches using the googletest library and this repo:

#include <gtest/gtest.h>

#define private public
#define protected public

#include <kalman/Matrix.hpp>
#include <Eigen/Cholesky>
#include <chrono>
#include <iostream>

using namespace Kalman;
using namespace std::chrono;

typedef float T;
typedef high_resolution_clock Clock;

TEST(Cholesky, inverseTiming) {
    Matrix<T, Dynamic, Dynamic> L;
    Matrix<T, Dynamic, Dynamic> S;
    Matrix<T, Dynamic, Dynamic> Sinv_method1;
    Matrix<T, Dynamic, Dynamic> Sinv_method2;
    int Nmin = 2;
    int Nmax = 128;
    int N(Nmin);

    while (N <= Nmax) {

        L.resize(N, N);
        L.setRandom();
        S.resize(N, N);
        // create a random NxN SPD matrix
        S = L*L.transpose();
        std::cout << "\n";
        std::cout << "+++++++++++++++++++++++++ N = " << N << " +++++++++++++++++++++++++++++++++++++++" << std::endl;
        auto t1 = Clock::now();
        Sinv_method1.resize(N, N);
        Sinv_method1 = S.inverse();
        auto dt1 = Clock::now() - t1;
        std::cout << "Method 1 took " << duration_cast<microseconds>(dt1).count() << " usec" << std::endl;
        auto t2 = Clock::now();
        Sinv_method2.resize(N, N);
        Sinv_method2 = S.llt().solve(Matrix<T, Dynamic, Dynamic>::Identity(N, N));
        auto dt2 = Clock::now() - t2;
        std::cout << "Method 2 took " << duration_cast<microseconds>(dt2).count() << " usec" << std::endl;
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                EXPECT_NEAR( Sinv_method1(i, j), Sinv_method2(i, j), 1e-3 );
            }
        }

        N *= 2;
        std::cout << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" << std::endl;
        std::cout << "\n";
    }
}

What the above example showed me was that, for my size problem, the speedup was negligible using method2 whereas the lack of accuracy (using the .inverse() call as the benchmark) was noticeable.

Tellurate