BP-Tools

Implementation of the blocking preconditioning for the unilevel block Toeplitz matrices.

🐉 Authors: Samuele Ferri, Valerio Loi

📜 Reference: Blocking structures, approximation, and preconditioning

📑 Dependencies: Python $\geq$ 3.11, matplotlib 3.10, numpy 2.2.4

📌 Version: 1.0

Introduction

The scope of this package is to give an easy way to build the blocking preconditioner (see reference) from a unilevel block matrix. By default it is supposed that the input matrix is of the form

where

• diagonal blocks $A_{ii}$, for $i=1,\dots, \nu$, are $sn_i\times tn_i$ Toeplitz matrices {$T_{n_i}(f_{i,i})$};
• off-diagonal blocks $A_{ij}$, for $i\neq j$, are $sn_{i}\times tn_{j}$ rectangular matrices $T_{n_i,n_j}(f_{i,j})$;
• $f_{i,j}$, $i,j=1,\dots,\nu$, are given functions belonging to $L^1([-\pi,\pi],{\mathbb{C}^{s\times t}})$.

Moreover, the blocks' sizes have to follow the next two assumptions:

• The parameters $\nu, s,t$ are fixed independent of $n$. Moreover, $\nu\ge 2$ and $s,t\ge 1$;
• $\lim_{n,n_i\rightarrow \infty} \frac{n_i}{n}=c_i$ {with} $c_i\in (0,1)$, $i=1,\dots,\nu$, {and} $c_1+c_2+\cdots + c_\nu=1$.

The preconditioner is built by "cutting" the matrix with the cutting principle and then by substituting each block of the cutted matrix with its associated circulant matrix.

The preconditioner for a unilevel $2\times 2$ block matrix. White spaces represent blocks of 0.

Cutting principle

According to the paper, the input matrix is cutted according the cutting principle. Each rectangular block along the the off-diagonals of the matrix $A_n$ is replaced with

Then, assuming that the sizes $n_1,\dots,n_\nu$ can be written as $n_j=m_j n(m)+o(n(m))$, $n(m)=\frac{n}{m}$ with $m$ a fixed positive integer, the cutting principle substitutes:

• if $n_j \le n_k$, $T_{n_{j}}(f)$ is replaced by $m_j$ copies of $T_{n(m)}(f)$, that is, $$\left[I_{m_j-1} \otimes T_{n(m)}(f)\right] \oplus X_{n(m),j,k},$$
• if $n_k \le n_j$, $T_{n_{k}}(f)$ is replaced by $m_k$ copies of $T_{n(m)}(f)$, that is, $$\left[I_{m_k-1} \otimes T_{n(m)}(f)\right] \oplus X_{n(m),j,k},$$

where $X_{n(m),j,k}$ is a matrix of size $n(m) + o(n(m))$, obtained by neglecting or adding, the last $o(n(m))$ rows and columns in $T_{n(m)}(f)$.

Application of the cutting principle to a unilevel $2\times 2$ block matrix

Usage assumptions

For the Python implementation it is supposed that the input matrix is a list of list of numpy arrays.

Main functions from src/cutter.py

• Cutter: wrapper that handles the input/output of the cutting procedure;
• cut_Matrix: true cutter. This function takes a matrix in input and returns the cutted matrix according to the cutting principle;
• Get_Circulant: wrapper that handles the input/output of the evaluation of the preconditioner;
• eval_Circulant: evaluates the block-circulant preconditioner of the cutted input block toepliz matrix.