Hierarchical Matrices

Concepts

Transposition

First, some general principles about how transposition is handled in butterfly:

• By default, “the transpose” refers to the Hermitian transpose. This is the same behavior as the ' operator in MATLAB, but different from NumPy’s .T property. That is, for a real matrix, the matrix is simply transposed; for a complex matrix, the matrix is transposed and its components are conjugated. Unfortunately, NumPy lacks something like a .H property (although this might change at some point—see this issue). Our view is that the Hermitian transpose is nearly always what is desired when working with complex matrices. In the rare case that the “true” transpose of a complex matrix is needed, and exception can be carved out.

Implementing consistent behavior for transposition in a hierarchical matrix library is tricky. Recall that the transpose of a block matrix satisfies:

\[\begin{split}\begin{bmatrix} A_{11} & \cdots & A_{1n} \\ \vdots & \ddots & \vdots \\ A_{m1} & \cdots & A_{mn} \end{bmatrix}^* = \begin{bmatrix} A_{11}^* & \cdots & A_{m1}^* \\ \vdots & \ddots & \vdots \\ A_{1n}^* & \cdots & A_{mn}^* \end{bmatrix}\end{split}\]

The transpose of a hierarchical block matrix follows by recursive application of this equation. This is simple enough mathematically, but deciding what to do when a function like bfMatTranspose is applied to an argument with a hierarchical block structure is complicated.