Determinant manipulation

Detailed Description

Manipulating determinants efficiently.

The weight of a MC configuration in CTQMC solvers is often given in terms of the determinant of one or more matrices such that the acceptance probability is a ratio of these determinants. It is therefore important to be able to efficiently compute these determinants and ratios of determinants.

Let \( F^{(n)} \) be the \( n \times n \) matrix that we are interested in. We assume that the elements of the matrix can be written as \( F^{(n)}_{ij} = f(x_i, y_j) \), where \( f \) is the callable object and \(\mathbf{x} \) and \( \mathbf{y} \) are vectors of size \( n \) that contain the arguments for \( f \) and therefore determine the contents of the matrix.

In the following, we will not work directly with the matrix \( F^{(n)} \) but with \( G^{(n)} \) which has its rows and columns permuted w.r.t. \( F^{(n)} \), i.e. \( F^{(n)} = P^{(n)}_r G^{(n)} P^{(n)}_c \). \( P^{(n)}_r \) and \( P^{(n)}_c \) are permutation matrices that permute the rows and columns of \( G^{(n)} \) to restore the original matrix. This gives us more flexibility when adding, removing, or modifying rows and columns.

Suppose we know the matrix \( G^{(n)} \) and its determinant \( \det(G^{(n)}) \) and that we want to add \( k \) new rows and columns to the matrix. We can write the resulting matrix as

\[ G^{(n+k)} = \begin{bmatrix} G^{(n)} & B \\ C & D \end{bmatrix} = \begin{bmatrix} [M^{(n)}]^{-1} & B \\ C & D \end{bmatrix} = [M^{(n+k)}]^{-1} \; . \]

Here, we have introduced the inverse matrix \( M^{(n)} = [G^{(n)}]^{-1} \) and the matrices \( B \), \( C \), and \( D \) which are of size \( n \times k \), \( k \times n \), and \( k \times k \), respectively. They contain the elements of the new rows and columns.

By making use of the block structure of the matrix (see also Wikipedia), the inverse matrix takes the form

\[ M^{(n+k)} = \begin{bmatrix} M^{(n)} + M^{(n)} B (D - C M^{(n)} B)^{-1} C M^{(n)} & -M^{(n)} B (D - C M^{(n)} B)^{-1} \\ -(D - C M^{(n)} B)^{-1} C M^{(n)} & (D - C M^{(n)} B)^{-1} \end{bmatrix} = \begin{bmatrix} P & Q \\ R & S \end{bmatrix} \; , \]

and its determinant can be computed as

\[ \det(G^{(n+k)}) = \det(G^{(n)}) \det(D - C M^{(n)} B) = \det(G^{(n)}) \det(S^{-1}) \; . \]

Here, \( P \), \( Q \), \( R \), and \( S \) are matrices of size \( n \times n \), \( n \times k \), \( k \times n \), and \( k \times k \), respectively.

The original matrix \( F^{(n)} \) and its determinant can be obtained with \( F^{(n)} = P^{(n)}_r G^{(n)} P^{(n)}_c \) and \( \det(F^{(n)}) = \det(P^{(n)}_r) \det(G^{(n)}) det(P^{(n)}_c) = s^{(n)} \det(G^{(n)}) \), where \( s^{(n)} = \det(P^{(n)}_r) det(P^{(n)}_c) = \pm 1 \) is a sign associated with the permutation matrices.

So by keeping track of the inverse matrix \( M^{(n)} \), the determinant \( \det(G^{(n)}) \) and two additional permutation matrices that specify how the rows and columns have been permuted w.r.t. the original matrix, we can add, remove, or modify (a few) rows and columns fairly efficiently.

Classes
class	triqs::det_manip::det_manip< FunctionType >
	Manipulate determinants and ratios of determinants for CTQMC solvers. More...
class	triqs::det_manip::det_manip_basic< FunctionType >
	Simple reference implementation of determinant manipulation for CTQMC solvers. More...