I would try blockwise inversion.
https://en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion
Eigen uses an optimized routine to calculate the inverse of a 4x4 matrix, which is probably the best you're going to get. Try using that as much as possible.
http://www.eigen.tuxfamily.org/dox/Inverse__SSE_8h_source.html
Top left: 8x8. Top right: 8x2. Bottom left: 2x8. Bottom right: 2x2. Invert the 8x8 using the optimized 4x4 inversion code. The rest is matrix products.
EDIT: Using 6x6, 6x4, 4x6, and 4x4 blocks has shown to be a bit faster than what I described above.
using namespace Eigen;
template<typename Scalar, int tl_size, int br_size>
Matrix<Scalar, tl_size + br_size, tl_size + br_size> blockwise_inversion(const Matrix<Scalar, tl_size, tl_size>& A, const Matrix<Scalar, tl_size, br_size>& B, const Matrix<Scalar, br_size, tl_size>& C, const Matrix<Scalar, br_size, br_size>& D)
{
Matrix<Scalar, tl_size + br_size, tl_size + br_size> result;
Matrix<Scalar, tl_size, tl_size> A_inv = A.inverse().eval();
Matrix<Scalar, br_size, br_size> DCAB_inv = (D - C * A_inv * B).inverse();
result.topLeftCorner<tl_size, tl_size>() = A_inv + A_inv * B * DCAB_inv * C * A_inv;
result.topRightCorner<tl_size, br_size>() = -A_inv * B * DCAB_inv;
result.bottomLeftCorner<br_size, tl_size>() = -DCAB_inv * C * A_inv;
result.bottomRightCorner<br_size, br_size>() = DCAB_inv;
return result;
}
template<typename Scalar, int tl_size, int br_size>
Matrix<Scalar, tl_size + br_size, tl_size + br_size> my_inverse(const Matrix<Scalar, tl_size + br_size, tl_size + br_size>& mat)
{
const Matrix<Scalar, tl_size, tl_size>& A = mat.topLeftCorner<tl_size, tl_size>();
const Matrix<Scalar, tl_size, br_size>& B = mat.topRightCorner<tl_size, br_size>();
const Matrix<Scalar, br_size, tl_size>& C = mat.bottomLeftCorner<br_size, tl_size>();
const Matrix<Scalar, br_size, br_size>& D = mat.bottomRightCorner<br_size, br_size>();
return blockwise_inversion<Scalar,tl_size,br_size>(A, B, C, D);
}
template<typename Scalar>
Matrix<Scalar, 10, 10> invert_10_blockwise_8_2(const Matrix<Scalar, 10, 10>& input)
{
Matrix<Scalar, 10, 10> result;
const Matrix<Scalar, 8, 8>& A = input.topLeftCorner<8, 8>();
const Matrix<Scalar, 8, 2>& B = input.topRightCorner<8, 2>();
const Matrix<Scalar, 2, 8>& C = input.bottomLeftCorner<2, 8>();
const Matrix<Scalar, 2, 2>& D = input.bottomRightCorner<2, 2>();
Matrix<Scalar, 8, 8> A_inv = my_inverse<Scalar, 4, 4>(A);
Matrix<Scalar, 2, 2> DCAB_inv = (D - C * A_inv * B).inverse();
result.topLeftCorner<8, 8>() = A_inv + A_inv * B * DCAB_inv * C * A_inv;
result.topRightCorner<8, 2>() = -A_inv * B * DCAB_inv;
result.bottomLeftCorner<2, 8>() = -DCAB_inv * C * A_inv;
result.bottomRightCorner<2, 2>() = DCAB_inv;
return result;
}
template<typename Scalar>
Matrix<Scalar, 10, 10> invert_10_blockwise_6_4(const Matrix<Scalar, 10, 10>& input)
{
Matrix<Scalar, 10, 10> result;
const Matrix<Scalar, 6, 6>& A = input.topLeftCorner<6, 6>();
const Matrix<Scalar, 6, 4>& B = input.topRightCorner<6, 4>();
const Matrix<Scalar, 4, 6>& C = input.bottomLeftCorner<4, 6>();
const Matrix<Scalar, 4, 4>& D = input.bottomRightCorner<4, 4>();
Matrix<Scalar, 6, 6> A_inv = my_inverse<Scalar, 4, 2>(A);
Matrix<Scalar, 4, 4> DCAB_inv = (D - C * A_inv * B).inverse().eval();
result.topLeftCorner<6, 6>() = A_inv + A_inv * B * DCAB_inv * C * A_inv;
result.topRightCorner<6, 4>() = -A_inv * B * DCAB_inv;
result.bottomLeftCorner<4, 6>() = -DCAB_inv * C * A_inv;
result.bottomRightCorner<4, 4>() = DCAB_inv;
return result;
}
Here are the results of one bench mark run using one million Eigen::Matrix<double,10,10>::Random()
matrices and Eigen::Matrix<double,10,1>::Random()
vectors. In all my tests, my inverse is always faster. My solve routine involves computing the inverse and then multiplying it by a vector. Sometimes its faster than Eigen, sometimes its not. My bench marking method may be flawed (didn't disable turbo boost, etc). Also, Eigen's random functions may not representative of real data.
- Eigen partial pivot inverse: 3036 milliseconds
- My inverse with 8x8 upper block: 1638 milliseconds
- My inverse with 6x6 upper block: 1234 milliseconds
- Eigen partial pivot solve: 1791 milliseconds
- My solve with 8x8 upper block: 1739 milliseconds
- My solve with 6x6 upper block: 1286 milliseconds
I am very interested to see if anyone can optimize this further, as I have a finite element application which inverts a gazillion 10x10 matrices (and yes, I do need individual coefficients of the inverse so directly solving a linear system is not always an option).