remarkRemark hypothesisHypothesis claimClaim Symbol-based multigrid methods
for Block structuresMatthias Bolten, Marco Donatelli, Paola Ferrari, Isabella
Furci

# A symbol based analysis for multigrid methods for
Block-Circulant and Block-Toeplitz Systems ††thanks: Submitted to the editors
DATE. This work was supported by Gruppo Nazionale per il Calcolo Scientifico
(GNCS-INdAM).

Matthias Bolten Department of Mathematics and Informatics. University of
Wuppertal, Wuppertal, Germany<EMAIL_ADDRESS>furci@uni-
wuppertal.de Marco Donatelli Department of Science and High Technology,
Insubria University, Insubria University, Como, Italy (,)
<EMAIL_ADDRESS><EMAIL_ADDRESS>Paola
Ferrari33footnotemark: 3 Isabella Furci22footnotemark: 2

###### Abstract

In the literature, there exist several studies on symbol-based multigrid
methods for the solution of linear systems having structured coefficient
matrices. In particular, the convergence analysis for such methods has been
obtained in an elegant form in the case of Toeplitz matrices generated by a
scalar-valued function. In the block-Toeplitz setting, that is, in the case
where the matrix entries are small generic matrices instead of scalars, some
algorithms have already been proposed regarding specific applications and a
first rigorous convergence analysis has been performed in [M. Donatelli, P.
Ferrari, I. Furci, D. Sesana, and S. Serra-Capizzano. Multigrid methods for
block-circulant and block-Toeplitz large linear systems: Algorithmic proposals
and two-grid optimality analysis. Numer. Linear Algebra Appl.]. However, with
the existent symbol-based theoretical tools, it is still not possible to prove
the convergence of many multigrid methods known in the literature. This paper
aims to generalize the previous results giving more general sufficient
conditions on the symbol of the grid transfer operators. In particular, we
treat matrix-valued trigonometric polynomials which can be non-diagonalizable
and singular at all points and we express the new conditions in terms of the
eigenvectors associated with the ill-conditioned subspace. Moreover, we extend
the analysis to the V-cycle method proving a linear convergence rate under
stronger conditions, which resemble those given in the scalar case. In order
to validate our theoretical findings, we present a classical block structured
problem stemming from a FEM approximation of a second order differential
problem. We focus on two multigrid strategies that use the geometric and the
standard bisection grid transfer operators and we prove that both fall into
the category of projectors satisfying the proposed conditions. In addition,
using a tensor product argument, we provide a strategy to construct efficient
V-cycle procedures in the block multilevel setting.

###### keywords:

Block-Toeplitz matrices, Multigrid methods, Finite element methods

15B05, 65N30, 65N55

##  1 Introduction

Linear systems with multilevel block-Toeplitz coefficient matrices arise in
the discretization of many differential and integral equations. Among them, we
mention the case of $\mathbb{Q}_{{r}}$ Lagrangian finite elements (FEM)
approximation of a second order differential problem [5] and the signal
restoration problems where some of the sampling data are not available [9].
When dealing with large multilevel and multilevel block-Toeplitz systems, the
performances (in terms of computational costs and iterations) of
preconditioners based on circulant approximations deteriorate [31]. This is
one of the many reasons why the class of multigrid methods is of great
interest for the solution of such systems [8, 16, 33].

Convergence results for multigrid methods are usually based on the local
Fourier analysis (LFA) [6], although several extensions and generalizations
have been recently proposed in the literature [15, 21, 26]. In [11] it was
proven that the convergence analysis of multigrid methods for circulant and
Toeplitz matrices [30, 32] is a linear algebra generalization of the LFA in
the case of the Galerkin approach. Indeed, it does not necessarily require a
differential operator and it can also be applied to integral problems with
applications such as signal and image processing [10]. For differential
problems with constant coefficients and uniform grids, the matrix algebra
approach leads to a condition on the symbols associated to the circulant
matrices analogous to the classical condition on the orders of the grid
transfer operators. In particular, such condition relates the order of the
zeros of the symbols associated to the coefficient matrix and the grid
transfer operators.

In this paper, we prove a generalization of such condition to block-symbols,
that is when the generating function $\mathbf{f}$ associated with the
coefficient matrix is a matrix-valued trigonometric polynomial. The block-
symbol has been previously investigated in the literature [12, 14, 23], but
many theoretical aspects have not yet been properly addressed. In particular,
a V-cycle convergence analysis is still missing and some classical grid
transfer operators do not satisfy the strong requirements of the two-grid
analysis in [12]. The main aim of the paper is to provide a complete
convergence analysis of multigrid methods for structured block-Toeplitz and
circulant systems under weak assumptions. In order to show the applicability
of our theory, we will consider classical multigrid strategies for
$\mathbb{Q}_{{r}}$ Lagrangian FEM in the case of uniform Cartesian grids.

First, we consider the Two Grid Method (TGM) and, according to the classical
Ruge-Stüben [29] convergence analysis, we focus on validating both a smoothing
property and an approximation property. The first is easily generalizable in
the block setting from the scalar case. Indeed, in [12] it has been proven
that it mainly affects the choice of the specific relaxation parameter for the
selected smoother. The validation of the approximation property for block
structured matrices approximation, instead, is non-trivial and it requires
additional hypotheses. In particular, the idea is to focus on the crucial
choice of conditions on the trigonometric polynomial $\mathbf{p}$ used to
construct the projector. In [12] the proof of the approximation property is
based on the validation of an additional commutativity requirement [12,
Section 4.1]. However, in some practical cases these conditions cannot be
satisfied. Hence, the main theorem of Section 4 provides less restrictive
conditions on $\mathbf{p}$. Indeed, differently from [12], the conditions are
expressed in terms of the eigenvectors associated with the ill-conditioned
subspace and permit to enlarge the class of suitable trigonometric polynomials
used to construct the projectors. Moreover, we provide some useful lemmas
which can further simplify the validation of the requirements, under specific
hypotheses that $\mathbf{p}$ often satisfies in the applications.

Another important result of the paper concerns the extension of the
theoretical findings to V-cycle methods. Indeed, following the proof of the
main theorem on the TGM convergence and the results in [25], it is possible to
obtain elegant conditions for the convergence and optimality of the V-cycle in
the block case. For the latter, a crucial point is the investigation of the
properties of the symbols at coarse levels, with a particular focus on the
orders of the zeros.

In order to validate our theoretical findings and show their applicability, we
present a classical block structured problem stemming from the
$\mathbb{Q}_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r}}$
Lagrangian FEM approximation of a second order differential problem. We focus
on two multigrid strategies that use the geometric projection operator and the
standard bisection grid transfer operator. We prove that both fall into the
category of projectors satisfying the proposed conditions, which lead to
convergence and optimality of multigrid methods [20, 14]. Finally, in Section
6 we provide the extension of the theory for block multilevel Toeplitz
matrices exploiting the properties of the Kronecker product.

The paper is organized as follows. In Section 2 we recall the basics of the
multigrid methods, with particular attention to the TGM convergence analysis
and on the general conditions that lead to the V-cycle optimality. In Section
3 we restrict the attention to the block setting recalling some properties of
block-circulant and block-Toeplitz matrices. In particular, we introduce the
main ingredients for an effective multigrid procedure that will be
investigated in Section 4. Here, we focus on the conditions which ensure the
convergence and optimality of the TGM for a linear system with coefficient
matrix generated by a matrix-valued trigonometric polynomial and we provide a
possible simplification for the validation of the conditions in practical
cases. In Subsection 4.2 we derive the conditions for convergence and
optimality also for the V-cycle. In Section 5 we present the two classical
multigrid strategies using the geometric projection operator and the standard
bisection grid transfer operator. Finally, in Section 6 we consider the
extension in the block multilevel case and we show how the results of previous
sections can be exploited and generalized.

##  2 Multigrid methods

Multigrid methods are efficient and robust iterative methods for solving
linear systems of the form

$A_{n}x_{n}=b_{n},$

where often, and as assumed in this paper, $A_{n}\in\mathbb{C}^{n\times n}$ is
positive definite [34]. The main idea is to combine a classical stationary
iterative method, called smoother, with a coarse grid correction having a
spectral behaviour complementary with respect to the smoother [7]. In order to
fix the notation for positive definite matrices, if $X\in\mathbb{C}^{n\times
n}$ is a positive definite matrix, $\|\cdot\|_{X}=\|X^{1/2}\cdot\|_{2}$
denotes the Euclidean norm weighted by $X$ on $\mathbb{C}^{n}$. If $X$ and $Y$
are Hermitian matrices, then the notation $X\leq Y$ means that $Y-X$ is a
nonnegative definite matrix. Given a matrix $X$ we denote by $X^{T}$ and
$X^{H}$ the transpose and the conjugate transpose matrix of $X$, respectively.

###  2.1 Two-grid method

Let $P_{n,k}\in\mathbb{C}^{n\times k}$, $k<n$, be a given full-rank matrix and
let us consider two stationary iterative methods: the method
$\mathcal{V}_{n,\rm{pre}}$, with iteration matrix ${V}_{n,\rm{pre}}$, and
$\mathcal{V}_{n,\rm{post}}$, with iteration matrix ${V}_{n,\rm{post}}$. An
iteration of a Two-Grid Method (TGM) is given in Algorithm 1.

Algorithm 1
TGM$(A_{n},\mathcal{V}_{n,\rm{pre}}^{\nu_{\rm{pre}}},\mathcal{V}_{n,\rm{post}}^{\nu_{\rm{post}}},P_{n,k},b_{n},x_{n}^{(j)})$

0\.
$\tilde{x}_{n}=\mathcal{V}_{n,\rm{pre}}^{\nu_{\rm{pre}}}(A_{n},{b}_{n},x_{n}^{(j)})$

1\. $r_{n}=b_{n}-A_{n}\tilde{x}_{n}$

2\. $r_{k}=P_{n,k}^{H}r_{n}$

3\. $A_{k}=P_{n,k}^{H}A_{n}P_{n,k}$

4\. Solve $A_{k}y_{k}=r_{k}$

5\. $\hat{x}_{n}=\tilde{x}_{n}+P_{n,k}y_{k}$

6\.
$x_{n}^{(j+1)}=\mathcal{V}_{n,\rm{post}}^{\nu_{\rm{post}}}(A_{n},{b}_{n},\hat{x}_{n})$

Steps $1.\rightarrow 5.$ define the “coarse grid correction” that depends on
the projecting operator $P_{n,k}$, while step $0.$ and step $6.$ consist,
respectively, in applying $\nu_{\rm{pre}}$ times a pre-smoother and
$\nu_{\rm{post}}$ times a post-smoother of the given iterative methods. Step
3. defines the coarser matrix $A_{k}$ according to the Galerkin approach which
ensures that the coarse grid correction is an algebraic projector and hence is
very useful for an algebraic study of the convergence of the method. Indeed,
the TGM is a stationary method defined by the following iteration matrix

$\displaystyle{\rm
TGM}(A_{n},V_{n,\rm{pre}}^{\nu_{\rm{pre}}},V_{n,\rm{post}}^{\nu_{\rm{post}}},P_{n,k})=V_{n,\rm{post}}^{\nu_{\rm{post}}}\left[I_{n}-P_{n,k}\left(P_{n,k}^{H}A_{n}P_{n,k}\right)^{-1}P_{n,k}^{H}A_{n}\right]V_{n,\rm{pre}}^{\nu_{\rm{pre}}}.$

######  Theorem 2.1.

([29]) Let $A_{n}$ be a positive definite matrix of size $n$ and let
$V_{n,{\rm post}},$ $V_{n,{\rm pre}}$ be defined as in the TGM algorithm.
Assume

  * (a)

$\exists\alpha_{\rm{pre}}>0\,:\;\|V_{n,\rm{pre}}x_{n}\|_{A_{n}}^{2}\leq\|x_{n}\|_{A_{n}}^{2}-\alpha_{\rm{pre}}\|V_{n,\rm{pre}}x_{n}\|_{A_{n}^{2}}^{2},\qquad\forall
x_{n}\in\mathbb{C}^{n},$

  * (b)

$\exists\alpha_{\rm{post}}>0\,:\;\|V_{n,\rm{post}}x_{n}\|_{A_{n}}^{2}\leq\|x_{n}\|_{A_{n}}^{2}-\alpha_{\rm{post}}\|x_{n}\|_{A_{n}^{2}}^{2},\qquad\forall
x_{n}\in\mathbb{C}^{n},$

  * (c)

$\exists\gamma>0\,:\;\min_{y\in\mathbb{C}^{k}}\|x_{n}-P_{n,k}y\|_{2}^{2}\leq\gamma\|x_{n}\|_{A_{n}}^{2},\qquad\forall
x_{n}\in\mathbb{C}^{n}.$

Then $\gamma\geq\alpha_{\rm{post}}$ and

$\displaystyle\|{\rm
TGM}(A_{n},V_{n,\rm{pre}},V_{n,\rm{post}},P_{n,k})\|_{A_{n}}\leq\sqrt{\frac{1-\alpha_{\rm{post}}/\gamma}{1+\alpha_{\rm{pre}}/\gamma}}<1.$

Conditions $(a)-(b)$ and $(c)$ are usually called “smoothing property” and
“approximation property”, respectively. Since $\alpha_{\rm{post}}$ and
$\gamma$ are independent of $n$, if the assumptions of Theorem 2.1 are
satisfied, then the resulting TGM exhibits a linear convergence. In other
words, the number of iterations in order to reach a given accuracy $\epsilon$
can be bounded from above by a constant independent of $n$ (possibly depending
on the parameter $\epsilon$). Moreover, if the projection and smoothing steps
have a computational cost lower or equal to the matrix-vector product with the
matrix $A_{n}$, then the TGM is optimal.

###  2.2 V-cycle method

For large $n$ a V-cycle method should be implemented. The standard V-cycle
method is obtained replacing the direct solution at step 4. with a recursive
call of the TGM applied to the coarser linear system
$A_{k_{\ell}}y_{k_{\ell}}=r_{k_{\ell}}$, where $\ell$ represents the level.
The recursion is usually stopped at level ${\ell_{\min}}$ when
$k_{\ell_{\min}}$ becomes small enough for solving cheaply step 4. with a
direct solver. In the following, as it is done in [25], we assume that we are
using the same iterative method as pre/post smoother, with same numbers of
iterative steps. We denote the iteration matrix by $V_{n_{\ell}}^{\nu}$. The
global iteration matrix ${\rm MGM}_{0}$ of the V-cycle method is recursively
defined as

$\displaystyle{\rm
MGM}_{\ell_{\min}}(A_{n_{\ell_{\min}}},V_{n_{\ell_{\min}}}^{\nu},V_{n_{\ell_{\min}}}^{\nu},P_{n_{\ell_{\min}},k_{\ell_{\min}}})=O_{n_{\ell_{\min}},n_{\ell_{\min}}},$
$\displaystyle{\rm
MGM}_{\ell}(A_{n_{\ell}},V_{n_{\ell}}^{\nu},V_{n_{\ell}}^{\nu},P_{n_{\ell},k_{\ell}})=$
$\displaystyle
V_{n_{\ell}}^{\nu}\left[I_{n_{\ell}}-P_{n_{\ell},k_{\ell}}\left(I_{n_{\ell}+1}-{\rm
MGM}_{\ell+1}\right)\left(P_{n_{\ell},k_{\ell}}^{H}A_{n_{\ell}}P_{n_{\ell},k_{\ell}}\right)^{-1}P_{n_{\ell},k_{\ell}}^{H}A_{n_{\ell}}\right]V_{n_{\ell}}^{\nu},$

for $\ell={\ell_{\min}-1},\dots,0$, where
$O_{n_{\ell_{\min}},n_{\ell_{\min}}}$ denotes the $n_{\ell_{\min}}\times
n_{\ell_{\min}}$ matrix of all zero components.

In order to prove the convergence and optimality of the V-cycle method, the
key ingredient is the analysis of the spectral radius of ${\rm MGM}_{0}$,
which is the iteration matrix at the finest level. In [25, Corollary 3.1] the
authors show the following relation

$\begin{split}\rho\left({\rm
MGM_{0}}(A_{n_{0}},V_{n_{0}}^{\nu},V_{n_{0}}^{\nu},P_{n_{0},k_{0}})\right)\leq
1-\min_{\ell}\frac{1-\rho\left({\rm
TGM}(A_{n_{0}},V_{n_{0}}^{\nu},V_{n_{0}}^{\nu},P_{n_{0},k_{0}})\right)}{\|\pi_{A_{n_{\ell}}}\|^{2}_{A_{n_{\ell}}(I_{n_{\ell}}-V_{n_{\ell}}^{2\nu})^{-1}},}\end{split},$

where
$\pi_{A_{n_{\ell}}}=P_{n_{\ell},k_{\ell}}(P_{n_{\ell},k_{\ell}}^{H}A_{n_{\ell}}P_{n_{\ell},k_{\ell}})^{-1}P_{n_{\ell},k_{\ell}}A_{n_{\ell}}.$
Hence, assuming that we choose smoothers and prolongation operators such that
the two grid optimality is guaranteed, i.e. $\rho\left({\rm
TGM}(A_{n_{0}},V_{n_{0}}^{\nu},V_{n_{0}}^{\nu},P_{n_{0},k_{0}})\right)<c<1$,
it is sufficient to prove that the following quantity is bounded

(1)
$\|\pi_{A_{n_{\ell}}}\|^{2}_{A_{n_{\ell}}(I_{n_{\ell}}-V_{n_{\ell}}^{2\nu})^{-1}}.$

In practice, the boundness of $\|\pi_{A_{n_{\ell}}}\|^{2}_{2}$ is usually
enough, reducing the convergence analysis to the study of the spectral
behaviour of the coarse grid correction operator.

######  Lemma 2.2.

Assume that there exists a positive $C$ independent of $n$ such that

(2) $\Lambda(A_{n_{\ell}})\subseteq(0,C],$

where $\Lambda(A_{n_{\ell}})$ denotes the spectrum of the matrix
$A_{n_{\ell}}$. Suppose that  one iteration of the Richardson method with the
damping parameter $\omega\in(0,2/C)$ both as pre-smoother and post-smoother is
applied. Then, the boundness of $\|\pi_{A_{n_{\ell}}}\|^{2}_{2}$ implies that
$\|\pi_{A_{n_{\ell}}}\|^{2}_{A_{n_{\ell}}(I_{n_{\ell}}-V_{n_{\ell}}^{2\nu})^{-1}}$
is bounded as well.

######  Proof 2.3.

Applying one step of pre-smoother and post-smoother, it holds

(3)
$\displaystyle\|\pi_{A_{n_{\ell}}}\|^{2}_{A_{n_{\ell}}(I_{n_{\ell}}-V_{n_{\ell}}^{2})^{-1}}$
$\displaystyle=$
$\displaystyle\left\|A_{n_{\ell}}^{1/2}(I_{n_{\ell}}-V_{n_{\ell}}^{2})^{-1/2}\pi_{A_{n_{\ell}}}\left(A_{n_{\ell}}^{1/2}(I_{n_{\ell}}-V_{n_{\ell}}^{2})^{-1/2}\right)^{-1}\right\|_{2}^{2}$
$\displaystyle\leq$
$\displaystyle\left\|A_{n_{\ell}}^{1/2}(I_{n_{\ell}}-V_{n_{\ell}}^{2})^{-1/2}\right\|_{2}^{2}\left\|\pi_{A_{n_{\ell}}}\right\|_{2}^{2}\left\|\left(A_{n_{\ell}}^{1/2}(I_{n_{\ell}}-V_{n_{\ell}}^{2})^{-1/2}\right)^{-1}\right\|_{2}^{2}.$

Since the smoother is the Richardson method with damping parameter $\omega$,
we can write

$\begin{split}&A_{n_{\ell}}^{1/2}(I_{n_{\ell}}-V_{n_{\ell}}^{2})^{-1/2}=A_{n_{\ell}}^{1/2}(I_{n_{\ell}}-\left(I_{n_{\ell}}-\omega
A_{n_{\ell}}\right)^{2})^{-1/2}=(2\omega
I_{n_{\ell}}-\omega^{2}A_{n_{\ell}})^{-1/2},\end{split}$

whose 2-norm is bounded if $\omega$ is such that
$2\omega-\omega^{2}\lambda_{j}(A_{n_{\ell}})>0,\,j=1,\dots,n_{\ell}.$
Equivalently,

$\begin{split}&\left(A_{n_{\ell}}^{1/2}(I_{n_{\ell}}-V_{n_{\ell}}^{2})^{-1/2}\right)^{-1}=(2\omega
I_{n_{\ell}}-\omega^{2}A_{n_{\ell}})^{1/2},\end{split}$

whose 2-norm is bounded for all $\omega\in(0,2/C)$ as $n$ increases thanks to
equation (2). Finally, thanks to inequality (3), the boundness of
$\|\pi_{A_{n_{\ell}}}\|^{2}_{2}$ implies that

$\|\pi_{A_{n_{\ell}}}\|^{2}_{A_{n_{\ell}}(I_{n_{\ell}}-V_{n_{\ell}}^{2\nu})^{-1}}$

is bounded as well.

##  3 Multigrid methods for block-circulant and block-Toeplitz matrices

In the present paper, we are interested in proposing an effective multigrid
method in the case where $A_{n}$ is a block-circulant or block-Toeplitz
matrix. Therefore, we recall some properties of these structured matrices.

###  3.1 Block-circulant and block-Toeplitz matrices

Let $\mathcal{M}_{d}$ be the linear space of the complex $d\times d$ matrices.
Given a function $\mathbf{f}:Q\to\mathcal{M}_{d}$, for $i=1,\dots,d$, we
denote by $\lambda_{i}(\mathbf{f})$ the eigenvalue functions of $\mathbf{f}$
and by $\lambda_{i}(\mathbf{f}(\theta))$ their evaluation at a point
$\theta\in Q$. The following lemma is derived from the results in [3, Section
VI.1] and provides the existence and continuity of the eigenvalue functions of
$\mathbf{f}$.

######  Lemma 3.1.

Let $\theta\rightarrow\mathbf{f}(\theta)$ be a continuous map from an interval
$Q$ into the space of $d\times d$ matrices such that the eigenvalues of
$\mathbf{f}(\theta)$ are real for all $\theta\in Q$. Then there exist
continuous functions
$\lambda_{1}(\mathbf{f}(\theta)),\lambda_{2}(\mathbf{f}(\theta)),\dots,\lambda_{d}(\mathbf{f}(\theta))$
that, for each $\theta\in Q$, are the eigenvalues of $\mathbf{f}(\theta)$.

Let $\mathbf{f}:Q\to\mathcal{M}_{d}$, with $Q=(-\pi,\pi)$. We say that
$\mathbf{f}\in L^{p}([-\pi,\pi])$ (resp. is measurable) if all its components
$f_{ij}:Q\to\mathbb{C},\ i,j=1,\ldots,d,$ belong to $L^{p}([-\pi,\pi])$ (resp.
are measurable) for $1\leq p\leq\infty$.

######  Definition 3.2.

Let the Fourier coefficients of a function $\mathbf{f}\in L^{p}([-\pi,\pi])$
be

$\displaystyle\hat{\mathbf{f}_{j}}:=\frac{1}{2\pi}\int_{Q}\mathbf{f}(\theta){\rm
e}^{-\iota
j\theta}d\theta\in\mathcal{M}_{d},\qquad\iota^{2}=-1,\,j\in\mathbb{Z}.$

Then, the block-Toeplitz matrix associated with f is the matrix with $d$
blocks of size $n$ and hence it has order $d\cdot n$ given by

$\displaystyle
T_{n}(\mathbf{f})=\sum_{|j|<n}J_{n}^{(j)}\otimes\hat{\mathbf{f}_{j}},$

where $\otimes$ denotes the (Kronecker) tensor product of matrices. The term
$J_{n}^{(j)}$ is the matrix of order $n$ whose $(i,k)$ entry equals $1$ if
$i-k=j$ and zero otherwise.

The set $\\{T_{n}(\mathbf{f})\\}_{n\in\mathbb{N}}$ is called the family of
block-Toeplitz matrices generated by $\mathbf{f}$, that in turn is referred to
as the generating function or the symbol of
$\\{T_{n}(\mathbf{f})\\}_{n\in\mathbb{N}}$. In the scalar case, when $d=1$, if
${f}$ is a trigonometric polynomial of degree lower than $n$, then we can
define the circulant matrix generated by $f$ by

$\displaystyle\mathcal{A}_{n}(f)=F_{n}\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize
diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{n}\end{smallmatrix}({f}(\theta_{i}^{(n)}))F_{n}^{H},$

where $\mathcal{I}_{n}=\\{0,\ldots,n-1\\}$ and
$F_{n}=\frac{1}{\sqrt{n}}\left[{\rm e}^{-\imath
j\theta_{i}^{(n)}}\right]_{i,j=0}^{n-1}$, with $\theta_{i}^{(n)}=\frac{2\pi
i}{n}$. Circulant matrices form an algebra of normal matrices. In the block-
case, $d>1$, if $\mathbf{f}:Q\to\mathcal{M}_{d}$ is a $d\times d$ matrix-
valued trigonometric polynomial, then the block-circulant matrix of order $dn$
generated by $\mathbf{f}$ is defined as

$\mathcal{A}_{n}(\mathbf{f})=(F_{n}\otimes
I_{d})\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{n}\end{smallmatrix}(\mathbf{f}(\theta_{i}^{(n)}))(F_{n}^{H}\otimes
I_{d}),$

where $\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{n}\end{smallmatrix}(\mathbf{f}(\theta_{i}^{(n)}))$
is the block-diagonal matrix where the block-diagonal elements are
$\mathbf{f}(\theta_{i}^{(n)})$.

###  3.2 Projectors for block structured matrices

For the convergence analysis of block-circulant and block-Toeplitz matrices,
previous results are based on the Ruge-Stüben theory [29] for TGM in Theorem
2.1, see [8, 22, 12]. The smoothing property is satisfied by damped Richardson
iteration simply choosing the damping parameter in the interval
$(0,2/\|\mathbf{f}\|_{\infty})$, see [12, Lemma 1]. The approximation property
$(c)$ requires a precise definition of $P_{n,k}$ and a detailed analysis.

The choice of prolongation and restriction operators fulfilling the
approximation condition is crucial for multigrid convergence and optimality.
In particular, the projector $P_{n,k}$ is chosen is order that

  * •

it projects the problem onto a coarser space by “cutting” the coefficient
matrix,

  * •

the resulting projected matrix should maintain the same block structure and
properties of the original matrix.

Let $K_{n,k}$ be the $n\times k$ downsampling matrix, such that:

n even:

$k=\frac{n}{2}$ and $K_{n,k}=K^{Odd}_{n,k}$,

n odd:

$k=\frac{n-1}{2}$ and $K_{n,k}=K^{Even}_{n,k}$,

with $K^{Odd}_{n,k}$ and $K^{Even}_{n,k}$ defined as

$K^{Odd}_{n,k}=\left[\begin{array}[]{cccccccc}1&&&&\\\ 0&&&&\\\ \vdots&1&&&\\\
&0&&&\\\ &\vdots&&&\vdots\\\ &&&&1\\\ &&&&0\\\ \end{array}\right]_{n\times
k},\qquad K^{Even}_{n,k}=\left[\begin{array}[]{cccccccc}0&&&&\\\ 1&&&&\\\
0&0&&&\\\ \vdots&1&&&\\\ &0&&&\\\ &\vdots&&&\\\ &&&&\vdots\\\ &&&&1\\\
&&&&0\\\ \end{array}\right]_{n\times k}.$

In particular, $K^{Odd}_{n,k}$ is the $n\times k$ matrix obtained by removing
the even rows from the identity matrix of size $n$, that is it keeps the odd
rows. On the other hand, $K^{Even}_{n,k}$ keeps the even rows. When $n$ is
even, $K^{Odd}_{n,k}$ performs the packaging of the Fourier frequencies since
it holds

$(K^{Odd}_{n,k})^{T}F_{n}=\frac{1}{\sqrt{2}}[F_{k}\,|\,F_{k}].$

This property of the Fourier matrix is the key to define a projector $P_{n,k}$
that preserves the block-circulant structure at the coarser levels. In the
rest of the paper, the projector will be denoted by $P^{d}_{n,k}$ since the
block-structured matrices have blocks of order $d$. Therefore, we define the
structure of the projecting operators $P^{d}_{n,k}$ for the block-circulant
matrix $\mathcal{A}_{n}(\mathbf{f})$ generated by a trigonometric polynomial
$\mathbf{f}:Q\rightarrow\mathcal{M}_{d}$ as follows. Let $n$ be even and of
the form $2^{t}$, $t\in\mathbb{N}$, such that the size of the coarser problem
is $k=\frac{n}{2}=2^{t-1}$. The projector $P^{d}_{n,k}$ is then constructed as
the product between a matrix $\mathcal{A}_{n}(\mathbf{p})$ in the algebra,
with $\mathbf{p}$ a proper trigonometric polynomial that will be defined in
the following sections, and a cutting matrix $K^{Odd}_{n,k}\otimes I_{d}$.
That is,

(4) $P^{d}_{n,k}=\mathcal{A}_{n}(\mathbf{p})(K^{Odd}_{n,k}\otimes I_{d}).$

The result of multiplying a $d\times d$ block matrix of dimension $dn\times
dn$ by $K^{Odd}_{n,k}\otimes I_{d}$ is a $d\times d$ block matrix where just
the even “block-columns” are maintained. We are left to determine the
conditions to be satisfied by $\mathcal{A}_{n}(\mathbf{p})$ (or better by its
generating function $\mathbf{p}$), in order to obtain a projector which is
effective in terms of convergence. Using the block-symbol analysis, sufficient
conditions have been proven in [12]. Unfortunately, such conditions are quite
strong and are not satisfied by the classical projector studied in Section 5.
Therefore, in the next section we prove weakly conditions on $\mathbf{p}$ that
provide an optimal multigrid method. The same strategy can be applied when we
deal with block-Toeplitz matrices generated by a matrix-valued trigonometric
polynomial, instead of block-circulant matrices. Indeed, the only thing that
should be adapted is the structure of the projector which slightly changes for
block-Toeplitz matrices, in order to preserve the structure at coarser levels.
Hence, for a matrix-valued trigonometric polynomial $\mathbf{p}$, the
projector matrix is $P^{d}_{n,k}=T_{n}(\mathbf{p})\left(K^{Even}_{n,k}\otimes
I_{d}\right).$ Note that in the Toeplitz case $n$ should be chosen odd and of
the form $2^{t}-1$, $t\in\mathbb{N}$, such that the size of the coarser
problem is $k=\frac{n-1}{2}=2^{t-1}-1$.

##  4 Multigrid convergence for block-Circulant matrices

Let $A_{N}=\mathcal{A}_{n}(\mathbf{f})$, $N=N(d,n)=dn$ and $n$ even, with
$\mathbf{f}$ matrix-valued trigonometric polynomial $\mathbf{f}\geq 0$. We
highlight that the theoretical results we derive are based on the hypothesis
that f is a trigonometric polynomial. This guarantees that the symbol at the
coarse levels maintains the same structure and properties of the symbol at the
finest one. However, in line with the scalar-valued case addressed in [30,
32], the proposed theory can be easily extended to the dense case where f
belongs to $L^{\infty}([-\pi,\pi])$, only requiring the additional hypothesis
that f has isolated zeros of finite order.

Let $P^{d}_{n,k}=\mathcal{A}_{n}(\mathbf{p})(K^{Odd}_{n,k}\otimes I_{d})$ with
$\mathbf{p}$ matrix-valued trigonometric polynomial. Suppose that there exist
unique $\theta_{0}\in[0,2\pi)$ and $\bar{\jmath}\in\\{1,\dots,d\\}$ such that

(5) $\left\\{\begin{array}[]{ll}\lambda_{j}(\mathbf{f}(\theta))=0,&\mbox{for
}\theta=\theta_{0}\mbox{ and }j=\bar{\jmath},\\\
\lambda_{j}(\mathbf{f}(\theta))>0,&{\rm otherwise}.\end{array}\right.$

The latter assumption means that the matrix $\mathbf{f}(\theta)$ has exactly
one zero eigenvalue in $\theta_{0}$ and it is positive definite in
$[0,2\pi)\backslash\\{\theta_{0}\\}$. Moreover, we have that the order of the
zero in $\theta_{0}$ must be even. As a consequence, the matrices $A_{N}$
could be singular and the ill-conditioned subspace is the eigenspace
associated with $\lambda_{\bar{\jmath}}(\mathbf{f}(\theta_{0}))$. On the other
hand, the block-Toeplitz matrices $T_{n}(\mathbf{f})$ are positive definite
with the same ill-conditioned subspace and become ill-conditioned as $N$
increases. Since $\mathbf{f}(\theta)$ is Hermitian, it can be diagonalized by
an orthogonal matrix $Q(\theta)$. Moreover, we are in the setting that the
eigenvalues and the eigenvectors of $\mathbf{f}$ are continuous functions in
the variable $\theta$ [24, 28]. We have

(6) $\begin{split}&\mathbf{f}(\theta)=Q(\theta)D(\theta)Q(\theta)^{H}=\\\
&\left[\begin{array}[]{@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}}q_{1}(\theta)&\dots&q_{\bar{\jmath}}(\theta)&\dots&q_{d}(\theta)\end{array}\right]\begin{bmatrix}\lambda_{1}(\mathbf{f}(\theta))&&&&&\\\
&\ddots&&&\\\ &&\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))&&\\\ &&&\ddots&\\\
&&&&\lambda_{d}(\mathbf{f}(\theta))\end{bmatrix}\left[\begin{array}[]{ccccccc}{q_{1}}^{H}(\theta)\\\
\hline\cr\vdots\\\ \hline\cr q_{\bar{\jmath}}^{H}(\theta)\\\
\hline\cr\vdots\\\ \hline\cr{q_{d}}^{H}(\theta)\end{array}\right],\end{split}$

where $q_{\bar{\jmath}}(\theta)$ is the eigenvector that generates the ill-
conditioned subspace since $q_{\bar{\jmath}}(\theta_{0})$ is the eigenvector
of $\mathbf{f}(\theta_{0})$ associated with
$\lambda_{\bar{\jmath}}(\mathbf{f}(\theta_{0}))=0$. Under the following
assumptions, we will prove that there are sufficient conditions to ensure the
linear convergence of the TGM.

In the next section—in particular Theorem 4.1—we will show that is sufficient
to choose $\mathbf{p}$ such that

  1. $(i)$

$\mathbf{p}(\theta)^{H}\mathbf{p}(\theta)+\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)>0\quad\forall\theta\in[0,2\pi),$

which implies that the trigonometric function

(7)
$\textbf{s}(\theta)=\mathbf{p}(\theta)\left(\mathbf{p}(\theta)^{H}\mathbf{p}(\theta)+\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)\right)^{-1}\mathbf{p}(\theta)^{H}$

is well-defined for all $\theta\in[0,2\pi)$,

  2. $(ii)$

$\textbf{s}(\theta_{0})q_{\bar{\jmath}}(\theta_{0})=q_{\bar{\jmath}}(\theta_{0}),$

  3. $(iii)$

$\lim_{\theta\rightarrow\theta_{0}}\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))^{-1}(1-\lambda_{\bar{\jmath}}(\textbf{s}(\theta)))=c,\quad
c\in\mathbb{R}.$

Note that the first condition does not depend on f and its spectral
properties, then it provides a certain freedom in the choice of the grid
transfer operator with respect to the problem. The second and third conditions
depend on the eigenvector associated to the singularity of f, which is known,
and the behaviour of the minimal eigenvalue function of f. The latter is a
scalar-valued function and its analytic properties can be investigated or
approximated with the preferred mathematical tools.

###  4.1 TGM optimality

The following theorem proves that conditions $(i)-(iii)$ imply the
approximation property $(c)$. Combining this result with the smoothing
property proved in [12], the optimality of the TGM follows from Theorem 2.1.

######  Theorem 4.1.

Consider the matrix $A_{N}:=\mathcal{A}_{n}(\mathbf{f})$, with $n$ even and
$\mathbf{f}\in\mathcal{M}_{d}$ matrix-valued trigonometric polynomial,
$\mathbf{f}\geq 0$, such that condition (5) is satisfied. Let $P^{d}_{n,k}$ be
the projecting operator defined as in equation (4) with
$\mathbf{p}\in\mathcal{M}_{d}$ trigonometric polynomial satisfying conditions
$(i)-(iii)$. Then, there exists a positive value $\gamma$ independent of $n$
such that inequality $(c)$ in Theorem 2.1 is satisfied.

######  Proof 4.2.

The first part of the proof takes inspiration from [12, Theorem 5.2]. We
report all the details for completeness, uniforming the notation. We remind
that in order to prove that there exists $\gamma>0$ independent of $n$ such
that for any $x_{N}\in\mathbb{C}^{N}$

(8)
$\displaystyle\min_{y\in\mathbb{C}^{K}}\|x_{N}-P^{d}_{n,k}y\|_{2}^{2}\leq\gamma\|x_{N}\|_{A_{N}}^{2},$

we can choose a special instance of $y$ in such a way that the previous
inequality is reduced to a matrix inequality in the sense of the partial
ordering of the real space of Hermitian matrices. For any
$x_{N}\in\mathbb{C}^{N}$, let
$\overline{y}\equiv\overline{y}(x_{N})\in\mathbb{C}^{K}$ be defined as
$\overline{y}=[(P^{d}_{n,k})^{H}P^{d}_{n,k}]^{-1}(P^{d}_{n,k})^{H}x_{N}.$ From
condition $(i)$ and [12, Proposition 4.2], it is straightforward that
$(P^{d}_{n,k})^{H}P^{d}_{n,k}$ is invertible. Therefore, (8) is implied by

$\displaystyle\|x_{N}-P^{d}_{n,k}\overline{y}\|_{2}^{2}\leq\gamma\|x_{N}\|_{A_{N}}^{2},$

where the latter is equivalent to the matrix inequality
$G_{N}(\mathbf{p})^{H}G_{N}(\mathbf{p})\leq\gamma A_{N}.$ with
$G_{N}(\mathbf{p})=I_{N}-P^{d}_{n,k}[(P^{d}_{n,k})^{H}P^{d}_{n,k}]^{-1}(P^{d}_{n,k})^{H}$.
By construction, the matrix $G_{N}(p)$ is a Hermitian unitary projector, in
fact
$G_{N}(\mathbf{p})^{H}G_{N}(\mathbf{p})=G_{N}(\mathbf{p})^{2}=G_{N}(\mathbf{p})$.
As a consequence, the preceding matrix inequality can be rewritten as

(9) $\displaystyle G_{N}(\mathbf{p})\leq\gamma\mathcal{A}_{n}(\mathbf{f}).$

We notice that
$\left(K^{Odd}_{n,k}\right)^{T}F_{n}=\frac{1}{\sqrt{2}}F_{k}I_{n,2}$, where
$I_{n,2}=\left[I_{k}|I_{k}\right]_{k\times n}$. Since we can decompose the
block-circulant matrix $\mathcal{A}_{n}(\mathbf{p})=(F_{n}\otimes
I_{d})\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{n}\end{smallmatrix}(\mathbf{p}(\theta_{i}^{(n)}))(F_{n}^{H}\otimes
I_{d})$, we have

$\displaystyle(P^{d}_{n,k})^{H}=\frac{1}{\sqrt{2}}(F_{k}\otimes
I_{d})(I_{n,2}\otimes
I_{d})\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{n}\end{smallmatrix}(\mathbf{p}(\theta_{i}^{(n)})^{H})(F_{n}^{H}\otimes
I_{d}),$

and the matrix $(F_{n}^{H}\otimes I_{d})G_{N}(\mathbf{p})(F_{n}\otimes I_{d})$
becomes

$\displaystyle(F_{n}^{H}\otimes I_{d})G_{N}(\mathbf{p})(F_{n}\otimes I_{d})$
$\displaystyle=I_{N}-\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize
diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{n}\end{smallmatrix}(\mathbf{p}(\theta_{i}^{(n)}))(I_{n,2}^{T}\otimes
I_{d})$
$\displaystyle\left[\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize
diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{k}\end{smallmatrix}(\mathbf{p}(\theta_{i}^{(n)})^{H}\mathbf{p}(\theta_{i}^{(n)})+\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})^{H}\mathbf{p}(\theta_{\tilde{\imath}}^{(n)}))\right]^{-1}$
$\displaystyle(I_{n,2}\otimes
I_{d})\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{n}\end{smallmatrix}(\mathbf{p}(\theta_{i}^{(n)})^{H})$

where $\tilde{\imath}=i+k$. Now, it is clear that there exists a suitable
permutation by rows and columns of $(F_{n}^{H}\otimes
I_{d})G_{N}(\mathbf{p})(F_{n}\otimes I_{d})$ such that we can obtain a
$2d\times 2d$ block-diagonal matrix of the form

$I_{N}-\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{k}\end{smallmatrix}\left[\begin{array}[]{c}\mathbf{p}(\theta_{i}^{(n)})\\\
\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})\end{array}\right]\\!\left[\begin{array}[]{c}(\mathbf{p}(\theta_{i}^{(n)})^{H}\mathbf{p}(\theta_{i}^{(n)})+\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})^{H}\mathbf{p}(\theta_{\tilde{\imath}}^{(n)}))^{-1}\end{array}\right]\\!\left[\begin{array}[]{cc}\mathbf{p}(\theta_{i}^{(n)})^{H}&\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})^{H}\end{array}\right].$

Therefore, by considering the same permutation by rows and columns of
$(F_{n}^{H}\otimes I_{d})\mathcal{A}_{n}(\mathbf{f})(F_{n}\otimes
I_{d})=\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{n}\end{smallmatrix}(\mathbf{f}(\theta_{i}^{(n)}))$,
condition (9) is equivalent to requiring that there exists $\gamma>0$
independent of $n$ such that, $\forall j=0,\ldots,k-1$

$\displaystyle I_{2d}-\left[\begin{array}[]{c}\mathbf{p}(\theta_{i}^{(n)})\\\
\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})\end{array}\right]\left[\begin{array}[]{c}(\mathbf{p}(\theta_{i}^{(n)})^{H}\mathbf{p}(\theta_{i}^{(n)})+\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})^{H}\mathbf{p}(\theta_{\tilde{\imath}}^{(n)}))^{-1}\end{array}\right]\left[\begin{array}[]{cc}\mathbf{p}(\theta_{i}^{(n)})^{H}&\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})^{H}\end{array}\right]$
$\displaystyle\leq\gamma\left[\begin{array}[]{cc}\mathbf{f}(\theta_{i}^{(n)})&\\\
&\mathbf{f}(\theta_{\tilde{\imath}}^{(n)})\end{array}\right].$

We define the set $\Omega(\theta_{0})=\\{\theta_{0},\theta_{0}+\pi\\}.$ Due of
the continuity of $\mathbf{p}$ and $\mathbf{f}$ it is clear that the preceding
set of inequalities can be reduced to requiring that a unique inequality of
the form

$\displaystyle I_{2d}-\left[\begin{array}[]{c}\mathbf{p}(\theta)\\\
\mathbf{p}(\theta+\pi)\end{array}\right]\left[\begin{array}[]{c}(\mathbf{p}(\theta)^{H}\mathbf{p}(\theta)+\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi))^{-1}\end{array}\right]$
$\displaystyle\left[\begin{array}[]{cc}\mathbf{p}(\theta)^{H}&\mathbf{p}(\theta+\pi)^{H}\end{array}\right]\leq\gamma\left[\begin{array}[]{cc}\mathbf{f}(\theta)&\\\
&\mathbf{f}(\theta+\pi)\end{array}\right]$

holds for all $\theta\in[0,2\pi)\backslash\Omega(\theta_{0})$. Let us define
$\textbf{q}(\theta)=(\mathbf{p}(\theta)^{H}\mathbf{p}(\theta)+\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi))^{-1}$.
By simple computations, the previous inequality becomes

(14) $\displaystyle
I_{2d}-\left[\begin{array}[]{cc}\mathbf{p}(\theta)\textbf{q}(\theta)\mathbf{p}(\theta)^{H}&\mathbf{p}(\theta)\textbf{q}(\theta)\mathbf{p}(\theta+\pi)^{H}\\\
\mathbf{p}(\theta+\pi)\textbf{q}(\theta)\mathbf{p}(\theta)^{H}&\mathbf{p}(\theta+\pi)\textbf{q}(\theta)\mathbf{p}(\theta+\pi)^{H}\end{array}\right]\leq\gamma\left[\begin{array}[]{cc}\mathbf{f}(\theta)&\\\
&\mathbf{f}(\theta+\pi)\end{array}\right].$

Let us define the matrix-valued function

$R(\theta)=\begin{bmatrix}\mathbf{f}(\theta)&\\\
&\mathbf{f}(\theta+\pi)\end{bmatrix}^{-\frac{1}{2}}\left[\begin{array}[]{cc}I_{d}-\mathbf{p}(\theta)\textbf{q}(\theta)\mathbf{p}(\theta)^{H}&-\mathbf{p}(\theta)\textbf{q}(\theta)\mathbf{p}(\theta+\pi)^{H}\\\
-\mathbf{p}(\theta+\pi)\textbf{q}(\theta)\mathbf{p}(\theta)^{H}&I_{d}-\mathbf{p}(\theta+\pi)\textbf{q}(\theta)\mathbf{p}(\theta+\pi)^{H}\end{array}\right]\cdot\\\
\cdot\begin{bmatrix}\mathbf{f}(\theta)&\\\
&\mathbf{f}(\theta+\pi)\end{bmatrix}^{-\frac{1}{2}}.$

Applying the Sylvester inertia law [19], we have that the relation (14) is
verified if

(15) $\displaystyle R(\theta)\leq\gamma I_{2d}$

is satisfied. If we prove that for every
$\theta\in[0,2\pi)\backslash\Omega(\theta_{0})$ the matrix $R(\theta)$ is
uniformly bounded in the spectral norm, then we have that there exists
$\gamma>0$ which bounds the spectral radius of $R(\theta)$ and then the latter
implies inequality (15). To show that the matrix $R(\theta)$ is uniformly
bounded in the spectral norm, we can rewrite $R(\theta)$ in components as

$\displaystyle R(\theta)=\begin{bmatrix}R_{1,1}(\theta)&R_{1,2}(\theta)\\\
R_{2,1}(\theta)&R_{2,2}(\theta)\end{bmatrix}=$
$\displaystyle\begin{bmatrix}\mathbf{f}^{-\frac{1}{2}}(\theta)(I_{d}-\mathbf{p}(\theta)\textbf{q}(\theta)\mathbf{p}(\theta)^{H})\mathbf{f}^{-\frac{1}{2}}(\theta)&\\!-\mathbf{f}^{-\frac{1}{2}}(\theta)\mathbf{p}(\theta)\textbf{q}(\theta)\mathbf{p}(\theta\\!+\\!\pi)^{H}\mathbf{f}^{-\frac{1}{2}}(\theta\\!+\\!\pi)\\\
-\mathbf{f}^{-\frac{1}{2}}(\theta\\!+\\!\pi)\mathbf{p}(\theta\\!+\\!\pi)\textbf{q}(\theta)\mathbf{p}(\theta)^{H}\mathbf{f}^{-\frac{1}{2}}(\theta)&\\!\mathbf{f}^{-\frac{1}{2}}(\theta\\!+\\!\pi)(I_{d}\\!-\\!\mathbf{p}(\theta\\!+\\!\pi)\textbf{q}(\theta)\mathbf{p}(\theta\\!+\\!\pi)^{H})\mathbf{f}^{-\frac{1}{2}}(\theta\\!+\\!\pi)\end{bmatrix}\\!\\!.$

The function
$\|R(\theta)\|_{2}:[0,2\pi)\backslash\Omega(\theta_{0})\rightarrow\mathbb{R}$
is continuous and, in order to show that $R(\theta)$ is uniformly bounded in
the spectral norm, Weierstrass theorem implies that it is sufficient to prove
that the following limits exist and are finite:

$\lim_{\theta\rightarrow\theta_{0}}\|R(\theta)\|_{2},\qquad\lim_{\theta\rightarrow\theta_{0}+\pi}\|R(\theta)\|_{2}.$

By definition, $R(\theta)$ is a Hermitian matrix for
$\theta\in[0,2\pi)\backslash\Omega(\theta_{0})$. Moreover, by direct
computation, one can verify that the matrix on the left-hand side of (14) is a
projector, having eigenvalues $0$ and $1$. Consequently, from the Sylvester
inertia law, it follows that $R(\theta)$ is a non-negative definite matrix. We
remark that in order to bound the spectral norm of a non-negative definite
matrix-valued function, it is sufficient to bound its trace. Hence, we check
that the spectral norms of the elements on the block diagonal of $R(\theta)$
are bounded. The latter is equivalent to verify that the limits

(16) $\lim_{\theta\rightarrow\theta_{0}}\|R_{1,1}(\theta)\|_{2},$ (17)
$\quad\lim_{\theta\rightarrow\theta_{0}}\|R_{2,2}(\theta)\|_{2},$ (18)
$\lim_{\theta\rightarrow\theta_{0}+\pi}\|R_{1,1}(\theta)\|_{2},$ (19)
$\quad\lim_{\theta\rightarrow\theta_{0}+\pi}\|R_{2,2}(\theta)\|_{2}$

exist and are finite, which in practice requires only the proof of (16).
Indeed, the finiteness of (17) and (18) is implied by the hypotheses on
$\mathbf{f}$, which is non-singular in $\theta_{0}+\pi$. The finiteness of
(19) can be proven as (16) taking into account that $R(\theta)$ is
$2\pi$-periodic. To prove (16) we note that for all
$\theta\in[0,2\pi)\backslash\Omega(\theta_{0})$, we can write

$\displaystyle\left\|R_{1,1}(\theta)\right\|_{2}=$
$\displaystyle\left\|\mathbf{f}^{-\frac{1}{2}}(\theta)(I_{d}-\mathbf{p}(\theta)\textbf{q}(\theta)\mathbf{p}(\theta)^{H})\mathbf{f}^{-\frac{1}{2}}(\theta)\right\|_{2}=\left\|\mathbf{f}^{-{1}}(\theta)-\mathbf{f}^{-\frac{1}{2}}(\theta)\textbf{s}(\theta)\mathbf{f}^{-\frac{1}{2}}(\theta)\right\|_{2},$

with $\textbf{s}(\theta)$ defined as in (7). Without loss of generality, we
can assume that $\bar{\jmath}=1$, that is $q_{1}(\theta_{0})$ is the
eigenvector of $\mathbf{f}(\theta_{0})$ associated with the eigenvalue $0$.
Indeed, if $\bar{\jmath}\neq 1$, it is sufficient to permute rows and columns
of $D(\theta_{0})$ in the factorization in (6) via a permutation matrix $\Pi$
which brings the diagonalization of $\mathbf{f}(\theta_{0})$ into the desired
form. Moreover, we can assume that $\|q_{1}(\theta_{0})\|_{2}=1$. From
condition $(i)$ we have that the matrix-valued function $\textbf{s}(\theta)$
is Hermitian for all $\theta\in[0,2\pi)$. In addition, from condition $(ii)$
and from the latter assumption on $\bar{\jmath}$, the matrix
$\textbf{s}(\theta)$ can be decomposed as
$\textbf{s}(\theta)=W_{s}(\theta)D_{s}(\theta)W_{s}^{H}(\theta)$ and

$\textbf{s}(\theta_{0})=\left[\begin{array}[]{@{\,}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\,}}q_{1}(\theta_{0})&w_{2}(\theta_{0})&\dots&w_{d}(\theta_{0})\end{array}\right]\begin{bmatrix}1\\\
&\lambda_{2}(\textbf{s}(\theta_{0}))\\\ &&\ddots\\\
&&&\lambda_{d}(\textbf{s}(\theta_{0}))\end{bmatrix}\left[\begin{array}[]{@{\,}c@{\,}}{q_{1}}^{H}(\theta_{0})\\\
\hline\cr{w_{2}}^{H}(\theta_{0})\\\ \hline\cr\vdots\\\
\hline\cr{w_{d}}^{H}(\theta_{0})\end{array}\right].$

Then, we can rewrite the quantity to bound as follows:

$\begin{split}&\lim_{\theta\rightarrow\theta_{0}}\|Q(\theta)D^{-1}(\theta)Q^{H}(\theta)-Q(\theta)D^{-\frac{1}{2}}(\theta)Q^{H}(\theta)W_{s}(\theta)D_{s}(\theta)W^{H}_{s}(\theta)Q^{H}(\theta)D^{-\frac{1}{2}}(\theta)Q^{H}(\theta)\|_{2}\\\
&=\lim_{\theta\rightarrow\theta_{0}}\|D^{-1}(\theta)-D^{-\frac{1}{2}}(\theta)Q^{H}(\theta)W_{s}(\theta)D_{s}(\theta)W^{H}_{s}(\theta)Q^{H}(\theta)D^{-\frac{1}{2}}(\theta)\|_{2}.\\\
\end{split}$

By definition of $Q(\theta_{0})$ and $W_{s}(\theta_{0})$, the vector
$q_{0}(\theta_{0})$ is orthogonal with respect to both $q_{j}(\theta_{0})$,
$w_{j}(\theta_{0})$, $j=2,\dots,d$. Denoting by $\textbf{0}_{d-1}$ the null
row vector of size $d-1$, we have

$\lim_{\theta\rightarrow\theta_{0}}Q^{H}(\theta)W_{s}(\theta)=\left[\begin{array}[]{
c c
}\begin{array}[]{c}q_{1}(\theta_{0})^{H}q_{1}(\theta_{0})\end{array}&\textbf{0}_{d-1}\\\
\textbf{0}_{d-1}^{T}&\begin{array}[]{cc}M(\theta_{0})\end{array}\end{array}\right],$

where $M(\theta)$ is a matrix-valued function which is well-defined and
continuous on $[0,2\pi]$. Then, since the eigenvalue functions
$\lambda_{i}(\mathbf{f}(\theta))^{-1}$, for $i=2,\dots,d$, are well-defined
and continuous on $[0,2\pi],$ see Lemma 3.1, the quantity to bound becomes

$\begin{split}&\left\|\\!\begin{bmatrix}\\!\underset{\theta\rightarrow\theta_{0}}{\lim}\lambda_{1}(\mathbf{f}(\theta))^{-1}(1-\lambda_{1}(\textbf{s}(\theta)))&\textbf{0}_{d-1}\\\
\textbf{0}_{d-1}^{T}&\begin{bmatrix}\lambda_{2}(\mathbf{f}(\theta_{0}))^{-1}\\\
&\\!\\!\\!\\!\ddots\\!\\!\\\
&&\lambda_{d}(\mathbf{f}(\theta_{0}))^{-1}\end{bmatrix}\\!\left(I_{d-1}\\!-\\!M(\theta_{0})M^{T}(\theta_{0})\right)\\!\end{bmatrix}\\!\right\|_{2}\end{split}\\!.$

Consequently, the thesis follows from condition $(iii)$.

######  Remark 4.3.

The proof of Theorem 4.1 requires that $\theta_{0}\neq\theta_{i}^{(n)}$ for
all $i$ and $n$. Nevertheless, in practice, our multigrid method works well
even if $\theta_{0}=\theta_{i}^{(n)}$ for a certain $i$ and $n$, as it can
happen in the circulant case. In such case the coefficient matrix $A_{N}$ is
singular but the multigrid method converges anyway, since it works on the
orthogonal complement of the eigenvector corresponding to the zero eigenvalue.
We could add a rank one correction, like the one used for scalar symbols in
[2], but this would only lead to unnecessary complication of notation, see
[1].

In practical applications choosing a $\mathbf{p}$ such that conditions $(ii)$
and $(iii)$ are verified could not be trivial. Hence, in the following,
assuming that $\mathbf{p}$ satisfies the condition $(i)$ so that the matrix-
valued function s is well-defined, we provide two useful results, Lemma
4.4-4.6, that can be used to construct $\mathbf{p}$ that fulfills condition
$(ii)$. Analogously, Lemma 4.9 shows how to deal with condition $(iii)$ under
some additional hypotheses on $\mathbf{p}$ and $\mathbf{f}$.

######  Lemma 4.4.

Let $\mathbf{f}$ be a matrix-valued trigonometric polynomial, $\mathbf{f}\geq
0$ that satisfies condition (5). Assume $\mathbf{p}$ is a matrix-valued
trigonometric polynomial such that condition $(i)$ is fulfilled, so that the
matrix-valued function s defined as in (7) is well-defined. Assume that the
eigenvector $q_{\bar{\jmath}}(\theta_{0})$ associate with the ill-conditioned
subspace of $\mathbf{f}(\theta_{0})$, i.e.,
$\mathbf{f}(\theta_{0})q_{\bar{\jmath}}(\theta_{0})=0q_{\bar{\jmath}}(\theta_{0})$,
is such that:

  1. 1.

$q_{\bar{\jmath}}(\theta_{0})$ is an eigenvector of $\mathbf{p}(\theta_{0})$,
associated to $\lambda^{(1)}_{\bar{\jmath}}\neq 0$ that is

$\mathbf{p}(\theta_{0})q_{\bar{\jmath}}(\theta_{0})=\lambda^{(1)}_{\bar{\jmath}}q_{\bar{\jmath}}(\theta_{0});$

  2. 2.

$q_{\bar{\jmath}}(\theta_{0})$ is an eigenvector of
$\mathbf{p}(\theta_{0}+\pi)$ associated with the zero eigenvalue, that is

$\mathbf{p}(\theta_{0}+\pi)q_{\bar{\jmath}}(\theta_{0})=0q_{\bar{\jmath}}(\theta_{0});$

  3. 3.

$q_{\bar{\jmath}}(\theta_{0})$ is an eigenvector of
$\mathbf{p}(\theta_{0})^{H}$, associated to $\lambda^{(2)}_{\bar{\jmath}}\neq
0$, that is

$\mathbf{p}(\theta_{0})^{H}q_{\bar{\jmath}}(\theta_{0})=\lambda^{(2)}_{\bar{\jmath}}q_{\bar{\jmath}}(\theta_{0}).$

Then condition $(ii)$ is satisfied.

######  Proof 4.5.

From all the hypotheses on $q_{\bar{\jmath}}(\theta_{0})$ and by direct
computation, we have
$\left(\mathbf{p}(\theta_{0})^{H}\mathbf{p}(\theta_{0})+\mathbf{p}(\theta_{0}+\pi)^{H}\mathbf{p}(\theta_{0}+\pi)\right)q_{\bar{\jmath}}(\theta_{0})=\lambda^{(1)}_{\bar{\jmath}}\lambda^{(2)}_{\bar{\jmath}}q_{\bar{\jmath}}(\theta_{0}).$
Then, by definition of $\textbf{s}(\theta)$ in (7), it holds that

$\displaystyle\textbf{s}(\theta_{0})q_{\bar{\jmath}}(\theta_{0})$
$\displaystyle=\mathbf{p}(\theta_{0})\left(\mathbf{p}(\theta_{0})^{H}\mathbf{p}(\theta_{0})+\mathbf{p}(\theta_{0}+\pi)^{H}\mathbf{p}(\theta_{0}+\pi)\right)^{-1}\mathbf{p}(\theta_{0})^{H}q_{\bar{\jmath}}(\theta_{0})$
$\displaystyle=\lambda_{\bar{\jmath}}^{(2)}\mathbf{p}(\theta_{0})\left(\mathbf{p}(\theta_{0})^{H}\mathbf{p}(\theta_{0})+\mathbf{p}(\theta_{0}+\pi)^{H}\mathbf{p}(\theta_{0}+\pi)\right)^{-1}q_{\bar{\jmath}}(\theta_{0})$
$\displaystyle=\lambda_{\bar{\jmath}}^{(2)}\frac{1}{\lambda^{(1)}_{\bar{\jmath}}\lambda^{(2)}_{\bar{\jmath}}}\mathbf{p}(\theta_{0})q_{\bar{\jmath}}(\theta_{0})=q_{\bar{\jmath}}(\theta_{0}).$

The next lemma provides other sufficient conditions to verify hypothesis
$(ii)$, if the projector is associated with a trigonometric polynomial
$\mathbf{p}$ which is non-singular in the considered point $\theta_{0}$.

######  Lemma 4.6.

With the assumption and notation of Lemma 4.4 where the condition 3. is
replaced with

  1. 3 bis.

$\mathbf{p}(\theta_{0})$ is non-singular.

Then condition $(ii)$ is satisfied.

######  Proof 4.7.

By definition of s in equation (7), we have

$\begin{split}\textbf{s}(\theta_{0})^{-1}&=\left(\mathbf{p}(\theta_{0})\left(\mathbf{p}(\theta_{0})^{H}\mathbf{p}(\theta_{0})+\mathbf{p}(\theta_{0}+\pi)^{H}\mathbf{p}(\theta_{0}+\pi)\right)^{-1}\mathbf{p}(\theta_{0})^{H}\right)^{-1}\\\
&=\mathbf{p}(\theta_{0})^{-H}\left(\mathbf{p}(\theta_{0})^{H}\mathbf{p}(\theta_{0})+\mathbf{p}(\theta_{0}+\pi)^{H}\mathbf{p}(\theta_{0}+\pi)\right)^{-1}\mathbf{p}(\theta_{0})^{-1}\\\
&=I_{d}+\mathbf{p}(\theta_{0})^{-H}\mathbf{p}(\theta_{0}+\pi)^{H}\mathbf{p}(\theta_{0}+\pi)\mathbf{p}(\theta_{0})^{-1}.\end{split}$

Then, it holds

$\begin{split}s(\theta_{0})^{-1}q_{\bar{\jmath}}(\theta_{0})=&\left[I_{d}+\mathbf{p}(\theta_{0})^{-H}\mathbf{p}(\theta_{0}+\pi)^{H}\mathbf{p}(\theta_{0}+\pi)\mathbf{p}(\theta_{0})^{-1}\right]q_{\bar{\jmath}}(\theta_{0})=\\\
&q_{\bar{\jmath}}(\theta_{0})+\frac{1}{\lambda_{\bar{\jmath}}^{(1)}}\mathbf{p}(\theta_{0})^{-H}\mathbf{p}(\theta_{0}+\pi)^{H}\mathbf{p}(\theta_{0}+\pi)q_{\bar{\jmath}}(\theta_{0})=q_{\bar{\jmath}}(\theta_{0})\end{split}$

and then condition $(ii)$ follows.

Finally, we present Lemma 4.9 to simplify the validation of condition $(iii)$
in possible applications. This provides some additional hypotheses on p and f
that can be considered when proving that condition $(iii)$ is satisfied. For
the aforementioned purpose we first introduce the following remark containing
algebraic calculations in order to speed up the proof of the lemma.

######  Remark 4.8.

Suppose that we can write $\mathbf{p}(\theta)$ as

$\mathbf{p}(\theta)=\left[\begin{array}[]{@{\,}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\,}}h_{1}(\theta)&h_{2}(\theta)&\dots&h_{d}(\theta)\end{array}\right]\begin{bmatrix}\lambda_{1}(\mathbf{p}(\theta))&\textbf{0}_{d-1}\\\
\textbf{0}_{d-1}^{T}&M(\theta)\end{bmatrix}\left[\begin{array}[]{@{\,}c@{\,}}{h_{1}}^{H}(\theta)\\\
\hline\cr{h_{2}}^{H}(\theta)\\\ \hline\cr\vdots\\\
\hline\cr{h_{d}}^{H}(\theta)\end{array}\right],$

where $M(\theta)\in\mathbb{C}^{(d-1)\times(d-1)},$ for each $\theta$,
$\lim_{\theta\rightarrow\theta_{0}}h_{1}(\theta+\pi)=q_{\bar{\jmath}}(\theta_{0})$,
and $h_{\jmath}(\theta_{0}+\pi)^{H}q_{\bar{\jmath}}(\theta_{0})=0,$ for
${\jmath}=2,\dots,d$. Then, we can write

$\begin{split}&\lim_{\theta\rightarrow\theta_{0}}\mathbf{p}(\theta+\pi)q_{\bar{\jmath}}(\theta_{0})=\\\
&\lim_{\theta\rightarrow\theta_{0}}\\!\left[\begin{array}[]{@{\,}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\,}}\\!h_{1}(\theta+\pi)&h_{2}(\theta+\pi)&\dots&h_{d}(\theta+\pi)\\!\end{array}\right]\\!\\!\begin{bmatrix}\lambda_{1}(\mathbf{p}(\theta+\pi))&\textbf{0}_{d-1}\\\
\textbf{0}_{d-1}^{T}&\\!\\!M(\theta+\pi)\end{bmatrix}\\!\\!\left[\begin{array}[]{@{\,}c@{\,}}{h_{1}}^{H}(\theta+\pi)\\\
\hline\cr{h_{2}}^{H}(\theta+\pi)\\!\\\ \hline\cr\vdots\\\
\hline\cr{h_{d}}^{H}(\theta+\pi)\end{array}\right]\\!\\!q_{\bar{\jmath}}(\theta_{0})\\!=\\\
&\lim_{\theta\rightarrow\theta_{0}}\\!\left[\begin{array}[]{@{\,}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\,}}\\!h_{1}(\theta+\pi)&h_{2}(\theta+\pi)&\dots&h_{d}(\theta+\pi)\\!\end{array}\right]\\!\\!\begin{bmatrix}\lambda_{1}(\mathbf{p}(\theta+\pi))&\textbf{0}_{d-1}\\\
\textbf{0}_{d-1}^{T}&\\!\\!M(\theta+\pi)\end{bmatrix}\\!\\!\left[\begin{array}[]{@{\,}c@{\,}}{q_{\bar{\jmath}}}^{H}(\theta_{0})\\\
\hline\cr{h_{2}}^{H}(\theta_{0}+\pi)\\\ \hline\cr\vdots\\\
\hline\cr{h_{d}}^{H}(\theta_{0}+\pi)\end{array}\right]\\!\\!q_{\bar{\jmath}}(\theta_{0})\\!=\\\
&\lim_{\theta\rightarrow\theta_{0}}\left[\begin{array}[]{@{\,}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\,}}\\!h_{1}(\theta+\pi)&h_{2}(\theta+\pi)&\dots&h_{d}(\theta+\pi)\\!\end{array}\right]\\!\\!\begin{bmatrix}\lambda_{1}(\mathbf{p}(\theta+\pi))&\textbf{0}_{d-1}\\\
\textbf{0}_{d-1}^{T}&\\!\\!M(\theta+\pi)\end{bmatrix}\\!\\!\begin{bmatrix}1\\\
0\\\ \vdots\\\ 0\end{bmatrix}=\\\
&\lim_{\theta\rightarrow\theta_{0}}\left[\begin{array}[]{@{\,}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\,}}h_{1}(\theta+\pi)&h_{2}(\theta+\pi)&\dots&h_{d}(\theta+\pi)\end{array}\right]\begin{bmatrix}\lambda_{1}(\mathbf{p}(\theta+\pi))\\\
0\\\ \vdots\\\ 0\end{bmatrix}=\\\
&\lim_{\theta\rightarrow\theta_{0}}\lambda_{1}(\mathbf{p}(\theta+\pi))h_{1}(\theta+\pi)=\lim_{\theta\rightarrow\theta_{0}}\lambda_{1}(\mathbf{p}(\theta+\pi))q_{\bar{\jmath}}(\theta_{0}).\end{split}$

######  Lemma 4.9.

Assume that $\mathbf{p}$ and $\mathbf{f}$ are matrix-valued functions which
satisfy the requirements of the Lemma 4.4. If

  1. 1.

$\lambda_{\bar{\jmath}}^{(1)}=\lambda_{\bar{\jmath}}^{(2)}=\lambda_{\bar{\jmath}},$

  2. 2.

$\lim_{\theta\rightarrow\theta_{0}}\frac{|\lambda_{\bar{\jmath}}(\mathbf{p}(\theta+\pi)|^{2}}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=c,$

then, the condition $(iii)$ of the Theorem 4.1 is satisfied. That is,

$\lim_{\theta\rightarrow\theta_{0}}\frac{1-\lambda_{\bar{\jmath}}(\textbf{s}(\theta))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=c.$

######  Proof 4.10.

From the hypotheses on $\textbf{s}(\theta)$, we have that
${\textbf{s}}(\theta)$ is equal to

$\begin{split}&\left[\begin{array}[]{@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}}w_{1}(\theta)&\dots&w_{\bar{\jmath}}(\theta)&\dots&w_{d}(\theta)\end{array}\right]\begin{bmatrix}\lambda_{1}({\textbf{s}}(\theta))&&&&\\\
&\ddots&&&\\\ &&\lambda_{\bar{\jmath}}({\textbf{s}}(\theta))&&\\\
&&&\ddots&\\\
&&&&\lambda_{d}({\textbf{s}}(\theta))\end{bmatrix}\left[\begin{array}[]{ccccccc}{w_{1}}^{H}(\theta)\\\
\hline\cr\vdots\\\ \hline\cr w_{\bar{\jmath}}^{H}(\theta)\\\
\hline\cr\vdots\\\ \hline\cr{w_{d}}^{H}(\theta)\end{array}\right]\end{split},$

where,
$\lim_{\theta\rightarrow\theta_{0}}w_{\jmath}(\theta)=q_{\bar{\jmath}}(\theta_{0}).$
By definition of s, we can write

$\begin{split}&\lim_{\theta\rightarrow\theta_{0}}\frac{1-\lambda_{\bar{\jmath}}(\textbf{s}(\theta))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=\\\
&\lim_{\theta\rightarrow\theta_{0}}\frac{1-w_{\jmath}(\theta)^{H}\mathbf{p}(\theta)\left(\mathbf{p}(\theta)^{H}\mathbf{p}(\theta)+\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)\right)^{-1}\mathbf{p}(\theta)^{H}w_{\jmath}(\theta)}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}.\end{split}$

Since
$\mathbf{p}(\theta_{0})q_{\bar{\jmath}}(\theta_{0})=\mathbf{p}(\theta_{0})^{H}q_{\bar{\jmath}}(\theta_{0})=\lambda_{\bar{\jmath}}q_{\bar{\jmath}}(\theta_{0})$,

$\begin{split}&\lim_{\theta\rightarrow\theta_{0}}\frac{1-\lambda_{\bar{\jmath}}(\textbf{s}(\theta))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=\\\
&\lim_{\theta\rightarrow\theta_{0}}\frac{1-|\lambda_{\bar{\jmath}}|q_{\bar{\jmath}}(\theta_{0})^{H}\left(\mathbf{p}(\theta)^{H}\mathbf{p}(\theta)+\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)\right)^{-1}q_{\bar{\jmath}}(\theta_{0})}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}.\end{split}$

Note that,

$\begin{split}&\lim_{\theta\rightarrow\theta_{0}}q_{\bar{\jmath}}(\theta_{0})^{H}\left(\mathbf{p}(\theta)^{H}\mathbf{p}(\theta)+\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)\right)q_{\bar{\jmath}}(\theta_{0})=\\\
&\lim_{\theta\rightarrow\theta_{0}}q_{\bar{\jmath}}(\theta_{0})^{H}\mathbf{p}(\theta)^{H}\mathbf{p}(\theta)q_{\bar{\jmath}}(\theta_{0})+\lim_{\theta\rightarrow\theta_{0}}q_{\bar{\jmath}}(\theta_{0})^{H}\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)q_{\bar{\jmath}}(\theta_{0})=\\\
&\lim_{\theta\rightarrow\theta_{0}}|\lambda_{\bar{\jmath}}|^{2}+q_{\bar{\jmath}}(\theta_{0})^{H}\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)q_{\bar{\jmath}}(\theta_{0}).\end{split}$

Then,

$\begin{split}&\lim_{\theta\rightarrow\theta_{0}}q_{\bar{\jmath}}(\theta_{0})^{H}\left(\mathbf{p}(\theta)^{H}\mathbf{p}(\theta)+\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)\right)^{-1}q_{\bar{\jmath}}(\theta_{0})=\\\
&\lim_{\theta\rightarrow\theta_{0}}\frac{1}{|\lambda_{\bar{\jmath}}|^{2}+q_{\bar{\jmath}}(\theta_{0})^{H}\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)q_{\bar{\jmath}}(\theta_{0})}.\end{split}$

Consequently, we can write

$\begin{split}&\lim_{\theta\rightarrow\theta_{0}}\frac{1-\lambda_{\bar{\jmath}}(\textbf{s}(\theta))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=\frac{1-\frac{|\lambda_{\bar{\jmath}}|^{2}}{|\lambda_{\bar{\jmath}}|^{2}+q_{\bar{\jmath}}(\theta_{0})^{H}\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)q_{\bar{\jmath}}(\theta_{0})}}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=\\\
&\lim_{\theta\rightarrow\theta_{0}}\frac{q_{\bar{\jmath}}(\theta_{0})^{H}\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)q_{\bar{\jmath}}(\theta_{0})}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))\left(|\lambda_{\bar{\jmath}}|^{2}+q_{\bar{\jmath}}(\theta_{0})^{H}\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)q_{\bar{\jmath}}(\theta_{0})\right)}=\\\
&c\lim_{\theta\rightarrow\theta_{0}}\frac{q_{\bar{\jmath}}(\theta_{0})^{H}\mathbf{p}(\theta+\pi)^{H}\mathbf{p}(\theta+\pi)q_{\bar{\jmath}}(\theta_{0})}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))},\end{split}$

where in the latter equality we used the fact that
$|\lambda_{\bar{\jmath}}|^{2}>0.$ Hence, from Remark 4.8, we have that

$\lim_{\theta\rightarrow\theta_{0}}\frac{1-\lambda_{\bar{\jmath}}(\textbf{s}(\theta))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=c\lim_{\theta\rightarrow\theta_{0}}\frac{|\lambda_{\bar{\jmath}}(\mathbf{p}(\theta+\pi)|^{2}}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}.$

Then, the thesis follows from hypothesis 2.

In conclusion, in order to prove that a considered symbol $\mathbf{p}$ is a
good choice to construct the grid transfer operator for the TGM method it is
sufficient to check if $\mathbf{p}$ satisfies:

  1. 1.

condition $(i)$,

  2. 2.

Lemma 4.4 or Lemma 4.6,

  3. 3.

Lemma 4.9.

###  4.2 V-cycle optimality

Following the proof of the Theorem 4.1 and the results in [25], it is possible
to derive also conditions for the convergence and optimality of the V-cycle in
the block case. Indeed, according to Lemma 2.2, it is sufficient to prove that
there exists a $\delta$ independent from $n$ such that, for all $\ell$,
$\|\pi_{A_{n_{\ell}}}\|_{2}\leq\delta,$ or, equivalently, that
$\|A_{n_{\ell}}^{1/2}P_{n_{\ell},k_{\ell}}(P_{n_{\ell},k_{\ell}}^{H}A_{n_{\ell}}P_{n_{\ell},k_{\ell}})^{-1}P_{n_{\ell},k_{\ell}}A_{n_{\ell}}^{1/2}\|_{2}\leq\delta,$
which is implied by

(20)
$A_{n_{\ell}}^{1/2}P_{n_{\ell},k_{\ell}}(P_{n_{\ell},k_{\ell}}^{H}A_{n_{\ell}}P_{n_{\ell},k_{\ell}})^{-1}P_{n_{\ell},k_{\ell}}A_{n_{\ell}}^{1/2}\leq\delta
I_{N}.$

As proved in [12, Proposition 1], all matrices $A_{n_{\ell}}$ have a block-
circulant structure and share the same spectral properties, in particular for
$\theta_{0}=0$, see also equation (21). Therefore, the following analysis
performed at the first level could be repeated unchanged at a generic level
$\ell$. Following the steps of the proof of Theorem 4.1, condition (20)
becomes

$\displaystyle\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{k}\end{smallmatrix}\left[\begin{array}[]{cc}\mathbf{f}(\theta_{i}^{(n)})&\\\
&\mathbf{f}(\theta_{\tilde{\imath}}^{(n)})\end{array}\right]^{\frac{1}{2}}\left[\begin{array}[]{c}\mathbf{p}(\theta_{i}^{(n)})\\\
\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})\end{array}\right]$
$\displaystyle\cdot\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize
diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{k}\end{smallmatrix}\left[\begin{array}[]{c}\mathbf{p}(\theta_{i}^{(n)})^{H}\mathbf{f}(\theta_{i}^{(n)})\mathbf{p}(\theta_{i}^{(n)})+\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})^{H}\mathbf{f}(\theta_{\tilde{\imath}}^{(n)})\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})\end{array}\right]^{-1}$
$\displaystyle\cdot\begin{smallmatrix}\vspace{-0.5ex}\textrm{\normalsize
diag}\\\
\vspace{-0.8ex}i\in\mathcal{I}_{k}\end{smallmatrix}\left[\begin{array}[]{cc}\mathbf{p}(\theta_{i}^{(n)})^{H}&\mathbf{p}(\theta_{\tilde{\imath}}^{(n)})^{H}\end{array}\right]\left[\begin{array}[]{cc}\mathbf{f}(\theta_{i}^{(n)})&\\\
&\mathbf{f}(\theta_{\tilde{\imath}}^{(n)})\end{array}\right]^{\frac{1}{2}}\leq\delta
I_{N}.$

The latter is equivalent to require that are bounded the components of the
matrix-valued function

$\begin{split}&Z(\theta)=\\\ &\left[\begin{array}[]{cc}\mathbf{f}(\theta)&\\\
&\mathbf{f}(\theta+\pi)\end{array}\right]^{\frac{1}{2}}\left[\begin{array}[]{c}\mathbf{p}(\theta)\\\
\mathbf{p}(\theta+\pi)\end{array}\right]\hat{\mathbf{f}}^{-1}(2\theta)\left[\begin{array}[]{cc}\mathbf{p}(\theta)^{H}&\mathbf{p}(\theta+\pi)^{H}\end{array}\right]\left[\begin{array}[]{cc}\mathbf{f}(\theta)&\\\
&\mathbf{f}(\theta+\pi)\end{array}\right]^{\frac{1}{2}},\end{split}$

where

(21)
$\displaystyle\hat{\mathbf{f}}(\theta)=\frac{1}{2}\left(\mathbf{p}\left(\frac{\theta}{2}\right)^{H}\mathbf{f}\left(\frac{\theta}{2}\right)\mathbf{p}\left(\frac{\theta}{2}\right)+\mathbf{p}\left(\frac{\theta}{2}+\pi\right)^{H}\mathbf{f}\left(\frac{\theta}{2}+\pi\right)\mathbf{p}\left(\frac{\theta}{2}+\pi\right)\right)$

is the generating function of
$\mathcal{A}_{k}(\hat{\mathbf{f}})=P_{n,k}^{H}\mathcal{A}_{n}(\mathbf{f})P_{n,k}$.
We have

$\begin{split}\|Z_{1,1}(\theta)\|&=\|\mathbf{f}(\theta)\mathbf{p}(\theta)\hat{\mathbf{f}}^{-1}(2\theta)\mathbf{p}(\theta)^{H}\mathbf{f}(\theta)\|\leq\\\
&\leq\|\mathbf{f}(\theta)\mathbf{p}(\theta)\hat{\mathbf{f}}^{-1}(2\theta)\|\|\mathbf{p}(\theta)^{H}\mathbf{f}(\theta)\|,\\\
\|Z_{2,2}(\theta)\|&=\|\mathbf{f}(\theta+\pi)\mathbf{p}(\theta+\pi)\hat{\mathbf{f}}^{-1}(2\theta)\mathbf{p}(\theta)^{H}\mathbf{f}(\theta+\pi)\|\leq\\\
&\leq\|\mathbf{f}(\theta+\pi)\|\|\mathbf{p}(\theta+\pi)\hat{\mathbf{f}}^{-1}(2\theta)\|\|\mathbf{p}(\theta+\pi)^{H}\mathbf{f}(\theta+\pi)\|,\\\
\|Z_{1,2}(\theta)\|,\|Z_{2,1}(\theta)\|&\leq\|\mathbf{f}(\theta)\mathbf{p}(\theta)\hat{\mathbf{f}}^{-1}(2\theta)\|\|\mathbf{p}(\theta+\pi)^{H}\mathbf{f}(\theta+\pi)\|.\end{split}$

Since $\mathbf{f}(\theta)$ and $\mathbf{p}(\theta)$ are trigonometric
polynomials, the quantities $\|\mathbf{p}(\theta)^{H}\mathbf{f}(\theta)\|$,
$\|\mathbf{f}(\theta+\pi)\|$ and
$\|\mathbf{p}(\theta+\pi)^{H}\mathbf{f}(\theta+\pi)\|$ are bounded. Hence, we
have to prove that

(22)
$\|\mathbf{f}(\theta)\mathbf{p}(\theta)\hat{\mathbf{f}}^{-1}(2\theta)\|<\infty,\quad\|\mathbf{p}(\theta+\pi)\hat{\mathbf{f}}^{-1}(2\theta)\|<\infty.$

Consequently, a key point is to investigate the properties of the generating
function at the coarse levels. The following lemma will be useful tools for
the aforementioned purpose.

######  Lemma 4.11.

Let $\mathbf{f}$ be defined as in Theorem 4.1 and $\hat{\mathbf{f}}$ be
defined as in formula (21). Assume that $q_{\bar{\jmath}}(\theta_{0})$ is the
eigenvector associated with the ill-conditioned subspace of
$\mathbf{f}(\theta_{0})$. In addition, assume that the eigenvector
$q_{\bar{\jmath}}(\theta_{0})$ is such that:

  1. (a)

$q_{\bar{\jmath}}(\theta_{0})$ is an eigenvector of $\mathbf{p}(\theta_{0})$,
associated to $\lambda^{(1)}\neq 0$ that is
$\mathbf{p}(\theta_{0})q_{\bar{\jmath}}(\theta_{0})=\lambda^{(1)}q_{\bar{\jmath}}(\theta_{0});$

  2. (b)

$q_{\bar{\jmath}}(\theta_{0})$ is an eigenvector of
$\mathbf{p}(\theta_{0}+\pi)$ associated with the zero eigenvalue, that is
$\mathbf{p}(\theta_{0}+\pi)q_{\bar{\jmath}}(\theta_{0})=0q_{\bar{\jmath}}(\theta_{0}).$

Then, the following properties are fulfilled:

  1. 1.

$\hat{\mathbf{f}}$ is an Hermitian matrix-valued trigonometric polynomial;

  2. 2.

$\hat{\mathbf{f}}(\theta)\geq 0$, $\forall\,\theta\in[0,2\pi]$;

  3. 3.

$\hat{\mathbf{f}}(2\theta_{0})q_{\bar{\jmath}}(\theta_{0})=0q_{\bar{\jmath}}(\theta_{0});$

  4. 4.

$\hat{\mathbf{f}}(\theta)>0,$ $\,\theta\neq 2\theta_{0}$;

  5. 5.

If

(23)
$\lim_{\theta\rightarrow\theta_{0}}\frac{\lambda_{\bar{\jmath}}^{2}(\mathbf{p}(\theta+\pi))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}<\infty,$

then

$\lim_{\theta\rightarrow\theta_{0}}\frac{\lambda_{\bar{\jmath}}(\hat{\mathbf{f}}(2\theta))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=c,\,c\neq
0\in\mathbb{R}.$

######  Proof 4.12.

  1. 1.

It is straightforward to see that $\hat{\mathbf{f}}$ is an Hermitian matrix-
valued trigonometric polynomial from its definition in (21). In particular,
$\hat{\mathbf{f}}$ is obtained by sums and products of the trigonometric
polynomials $\mathbf{p}$ and $\mathbf{f}$.

  2. 2.

Assume $y\in\mathbb{R}^{d}$, then we have

$y^{T}\hat{\mathbf{f}}y=\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}\right)^{H}\mathbf{f}\left(\frac{\theta}{2}\right)\mathbf{p}\left(\frac{\theta}{2}\right)y+\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}+\pi\right)^{H}\mathbf{f}\left(\frac{\theta}{2}+\pi\right)\mathbf{p}\left(\frac{\theta}{2}+\pi\right)y.$

By hypotheses, $\mathbf{f}(\frac{\theta}{2})$ and
$\mathbf{f}(\frac{\theta}{2}+\pi)$ are non negative matrices, then
$y^{T}\hat{\mathbf{f}}y\geq 0.$

  3. 3.

By definition, it holds

$\hat{\mathbf{f}}(2\theta_{0})q_{\bar{\jmath}}=\frac{1}{2}\mathbf{p}^{H}(\theta_{0})\mathbf{f}({\theta_{0}})\mathbf{p}(\theta_{0})q_{\bar{\jmath}}+\frac{1}{2}\mathbf{p}^{H}(\theta_{0}+\pi)\mathbf{f}(\theta_{0}+\pi)\mathbf{p}(\theta_{0}+\pi)q_{\bar{\jmath}}.$

The vector $q_{\bar{\jmath}}(\theta_{0})$ is the eigenvector of
$\mathbf{p}(\theta_{0}+\pi)$ and $\mathbf{f}(\theta_{0})$ associated with the
zero eigenvalue and it is the eigenvector of $\mathbf{p}(\theta_{0})$
associated with $\lambda^{(1)}$. Then, we have

$\hat{\mathbf{f}}(2\theta_{0})q_{\bar{\jmath}}=\frac{\lambda^{(1)}}{2}\mathbf{p}^{H}(\theta_{0})\mathbf{f}({\theta_{0}})q_{\bar{\jmath}}(\theta_{0})+0q_{\bar{\jmath}}(\theta_{0})=0q_{\bar{\jmath}}(\theta_{0}).$

  4. 4.

Assume $y\neq 0\in\mathbb{R}^{d}$, then we have

$y^{T}\hat{\mathbf{f}}y=\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}\right)^{H}\mathbf{f}\left(\frac{\theta}{2}\right)\mathbf{p}\left(\frac{\theta}{2}\right)y+\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}+\pi\right)^{H}\mathbf{f}\left(\frac{\theta}{2}+\pi\right)\mathbf{p}\left(\frac{\theta}{2}+\pi\right)y.$

From the proof of the second item we already know that
$y^{T}\hat{\mathbf{f}}y\geq 0,$ since both
$\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}\right)^{H}\mathbf{f}\left(\frac{\theta}{2}\right)\mathbf{p}\left(\frac{\theta}{2}\right)y$
and
$\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}+\pi\right)^{H}\mathbf{f}\left(\frac{\theta}{2}+\pi\right)\mathbf{p}\left(\frac{\theta}{2}+\pi\right)y$
are non negative. To prove that, for $\theta\neq 2\theta_{0}$,
$y^{T}\hat{\mathbf{f}}y>0,$ it is sufficient to show that if
$\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}\right)^{H}\mathbf{f}\left(\frac{\theta}{2}\right)\mathbf{p}\left(\frac{\theta}{2}\right)y=0$,
then
$\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}+\pi\right)^{H}\mathbf{f}\left(\frac{\theta}{2}+\pi\right)\mathbf{p}\left(\frac{\theta}{2}+\pi\right)y$
is different from 0 and, if
$\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}+\pi\right)^{H}\mathbf{f}\left(\frac{\theta}{2}+\pi\right)\mathbf{p}\left(\frac{\theta}{2}+\pi\right)y=0$,
then
$\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}\right)^{H}\mathbf{f}\left(\frac{\theta}{2}\right)\mathbf{p}\left(\frac{\theta}{2}\right)y\neq
0$. In the following we show the first fact, the latter can be proved in the
same way. We have that
$\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}\right)^{H}\mathbf{f}\left(\frac{\theta}{2}\right)\mathbf{p}\left(\frac{\theta}{2}\right)y=0$
if and only if $\mathbf{p}\left(\frac{\theta}{2}\right)y=0y$. Note that for
$\theta\neq 2\theta_{0}$, $\mathbf{f}(\theta/2)>0$, since, for
$\theta\neq\theta_{0}$, $\mathbf{f}(\theta)>0$. Moreover, if $\theta\neq
2\theta_{0}$, then for periodicity, $\theta\neq 2\theta_{0}-2\pi$, that is,
$\theta/2+\pi\neq\theta_{0}$. Consequently, $\mathbf{f}(\theta/2+\pi)>0$. If,
by contradiction,
$\frac{1}{2}y^{T}\mathbf{p}\left(\frac{\theta}{2}+\pi\right)^{H}\mathbf{f}\left(\frac{\theta}{2}+\pi\right)\mathbf{p}\left(\frac{\theta}{2}+\pi\right)y=0$,
then $\mathbf{p}(\theta/2+\pi)y=0y$, that cannot be satisfied, since, by
hypothesis $\mathbf{p}(\theta)$ verifies the condition $(i)$.

  5. 5.

Since $\hat{\mathbf{f}}(\theta)$ is Hermitian for every $\theta$, we can
assume $\hat{\mathbf{f}}(\theta)$ equals to

$\begin{split}&\left[\begin{array}[]{@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}}\\!v_{1}(\theta)&\dots&v_{\bar{\jmath}}(\theta)&\dots&v_{d}(\theta)\\!\end{array}\right]\\!\\!\begin{bmatrix}\lambda_{1}(\hat{\mathbf{f}}(\theta))&&&&\\\
&\\!\\!\ddots\\!\\!&&&\\\
&&\lambda_{\bar{\jmath}}(\hat{\mathbf{f}}(\theta))&&\\\
&&&\\!\\!\ddots\\!\\!&\\\
&&&&\lambda_{d}(\hat{\mathbf{f}}(\theta))\end{bmatrix}\\!\\!\left[\begin{array}[]{ccccccc}{v_{1}}^{H}(\theta)\\\
\hline\cr{v_{2}}^{H}(\theta)\\\ \hline\cr\vdots\\\ \hline\cr
v_{\bar{\jmath}}^{H}(\theta)\\\ \hline\cr\vdots\\\
\hline\cr{v_{d}}^{H}(\theta)\end{array}\right].\end{split}$

From property 3, we can assume, without loss of generality, that

(24)
$\lim_{\theta\rightarrow\theta_{0}}v_{\bar{\jmath}}(2\theta)=q_{\bar{\jmath}}(\theta_{0}).$

Consequently, we obtain

(25)
$\begin{split}&\lim_{\theta\rightarrow\theta_{0}}\\!\frac{\lambda_{\bar{\jmath}}(\hat{\mathbf{f}}(2\theta))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}\\!=\\!\lim_{\theta\rightarrow\theta_{0}}\\!\frac{v_{\bar{\jmath}}(2\theta)^{H}\hat{\mathbf{f}}(2\theta))v_{\bar{\jmath}}(2\theta)}{q_{\bar{\jmath}}(\theta){\mathbf{f}}(\theta)q_{\bar{\jmath}}(\theta)}\\!=\\!\frac{1}{2}\lim_{\theta\rightarrow\theta_{0}}\\!\\!\left(\\!\frac{v_{\bar{\jmath}}(2\theta)^{H}{\mathbf{p}}(\theta)^{H}\mathbf{f}(\theta)\mathbf{p}(\theta)v_{\bar{\jmath}}(2\theta)}{q_{\bar{\jmath}}(\theta){\mathbf{f}}(\theta)q_{\bar{\jmath}}(\theta)}+\right.\\\
&\left.\frac{v_{\bar{\jmath}}(2\theta)^{H}{\mathbf{p}}(\theta+\pi)^{H}\mathbf{f}(\theta+\pi)\mathbf{p}(\theta+\pi)v_{\bar{\jmath}}(2\theta)}{q_{\bar{\jmath}}(\theta){\mathbf{f}}(\theta)q_{\bar{\jmath}}(\theta)}\right)=\frac{1}{2}\frac{q_{\bar{\jmath}}(\theta_{0})^{H}{\mathbf{p}}(\theta_{0})^{H}\mathbf{f}(\theta_{0})\mathbf{p}(\theta_{0})q_{\bar{\jmath}}(\theta_{0})}{q_{\bar{\jmath}}(\theta_{0}){\mathbf{f}}(\theta_{0})q_{\bar{\jmath}}(\theta_{0})}+\\\
&\frac{1}{2}\lim_{\theta\rightarrow\theta_{0}}\frac{v_{\bar{\jmath}}(2\theta)^{H}{\mathbf{p}}(\theta+\pi)^{H}\mathbf{f}(\theta+\pi)\mathbf{p}(\theta+\pi)v_{\bar{\jmath}}(2\theta)}{q_{\bar{\jmath}}(\theta){\mathbf{f}}(\theta)q_{\bar{\jmath}}(\theta)},\end{split}$

where in the first term we used relation (24). Exploiting properties (a) and
(b) and Remark 4.8, we can write

(26)
$\begin{split}&\lim_{\theta\rightarrow\theta_{0}}\frac{\lambda_{\bar{\jmath}}(\hat{\mathbf{f}}(2\theta))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=\frac{1}{2}(\lambda^{(1)})^{2}+\frac{1}{2}{q_{\bar{\jmath}}(\theta_{0})^{H}\mathbf{f}(\theta_{0}+\pi)q_{\bar{\jmath}}(\theta_{0})}\left(\lim_{\theta\rightarrow\theta_{0}}\frac{\lambda_{\bar{\jmath}}^{2}(\mathbf{p}(\theta+\pi))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}\right),\end{split}$

where $\lambda_{\bar{\jmath}}^{2}(\mathbf{p}(\theta+\pi))$ is the eigenvalue
of $\mathbf{p}(\theta+\pi)$ associated to the eigenvector
$q_{\bar{\jmath}}(\theta_{0})$. Since the quantity
$\frac{1}{2}{q_{\bar{\jmath}}(\theta_{0})^{H}\mathbf{f}(\theta_{0}+\pi)q_{\bar{\jmath}}(\theta_{0})}$
is strictly positive and bounded by condition (5), property 5 is satisfied
under the hypotheses that

(27)
$\lim_{\theta\rightarrow\theta_{0}}\frac{\lambda_{\bar{\jmath}}^{2}(\mathbf{p}(\theta+\pi))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}<\infty.$

Passing from TGM to V-cycle, the hypothesis 2 in Lemma 4.9 has to be
strengthen removing the power two, similarly to the case of scalar symbol [1],
obtaining the condition

$\lim_{\theta\rightarrow\theta_{0}}\frac{|\lambda_{\bar{\jmath}}(\mathbf{p}(\theta+\pi))|}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=c.$

In fact, it leads to convergence and optimality even when dealing with V-cycle
with more than two grids.

######  Lemma 4.13.

Let $\mathbf{p}$ and $\mathbf{f}$ satisfy the hypothesis of Lemma 4.11. If

(28)
$\lim_{\theta\rightarrow\theta_{0}}\frac{|\lambda_{\bar{\jmath}}(\mathbf{p}(\theta+\pi))|}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=c,$

then the two bounds in (22), needed for the convergence and optimality of the
V-cycle, are verified.

######  Proof 4.14.

The condition (28) implies the hypothesis of the item 5 of Lemma 4.11, then we
have that the order of the zero at the coarse levels does not change, since it
brings to

(29)
$\lim_{\theta\rightarrow\theta_{0}}\frac{\lambda_{\bar{\jmath}}(\hat{\mathbf{f}}(2\theta))}{\lambda_{\bar{\jmath}}(\mathbf{f}(\theta))}=c,\,c\neq
0\in\mathbb{R},$

where $\hat{\mathbf{f}}(\theta)$ is given in (21). Hence, from direct
computation using the same techniques as in the proof of Theorem 4.1 and Lemma
4.11, we have that the quantity

$\|\mathbf{f}(\theta)\mathbf{p}(\theta)\hat{\mathbf{f}}^{-1}(2\theta)\|$

is bounded. Moreover, the limit bound in (29) implies that the second
condition in (22) can be replaced by

$\|\mathbf{p}(\theta+\pi){\mathbf{f}}^{-1}(2\theta)\|<\infty,$

which is given by (28).

##  5 Geometric Projectors

In the following we will apply the theoretical considerations from the
previous sections to problems arising from the discretization of partial
differential equations (PDEs). When PDEs are discretized with high order of
accuracy using the finite element method (FEM), block matrices arise
naturally. We consider finite elements with nodal bases, using a Cartesian
grid and Kronecker products of one-dimensional basis functions. For a problem
posed in $m$ dimensions discretized using Kronecker product of basis functions
of degree $r$ this automatically yields blocks of size $r^{m}\times r^{m}$. As
prolongation operators we have different choices, here we consider two: the
linear interpolation usually used in geometric multigrid methods for scalar
problems [34] and the prolongation obtained as the adjoint operator of the
restriction operator when considering the finite element basis functions [4].

###  5.1 $\mathbb{Q}_{r}$ Lagrangian FEM Stiffness Matrices

First we consider the $\mathbb{Q}_{r}$ Lagrangian FEM approximation of the
differential 1D problem, that is given by: Find $u$ such that

(30) $\begin{cases}&-u^{\prime\prime}(x)=\psi(x)\quad{\rm on}\,\,(0,1),\\\
&u(0)=u(1)=0,\end{cases}$

where $\psi(x)\in L^{2}\left(0,1\right)$. In this setting the weak formulation
on the problem is written as follows: Find $u\in H^{1}_{0}(0,1)$ such that
$a(u,v)=\langle\psi,v\rangle,\quad\forall v\in H^{1}_{0}(0,1),$ where
$a(u,v):=\int_{(0,1)}u^{\prime}(x)v^{\prime}(x)\,dx$ and
$\langle\psi,v\rangle:=\int_{(0,1)}\psi(x)v(x)\,dx$. For $r,n\geq 1$, we
define the space

(31) $V_{n}^{(r)}:=\\{\sigma\in\mathcal{C}\left([0,1]\right),\,{\rm
such}\,{\rm
that}\,\sigma{|_{\left[\frac{i}{n},\frac{i+1}{n}\right]}}\in\mathbb{P}_{r},\,\forall
i=0,\dots,n-1\\},$

where we denote by $\mathbb{P}_{r}$ the space of polynomials of degree less
than or equal to $r$. So the space $V_{n}^{(r)}$ represents the space of
continuous piecewise polynomial functions. Starting from $V_{n}^{(r)}$, we
consider its subspace of functions that vanish on the boundary, defined by
$W_{n}^{(r)}:=\\{\sigma\in V_{n}^{(r)},\,{\rm such}\,{\rm
that}\,\sigma(0)=\sigma(1)=0\\}.$ Note that $W_{n}^{(r)}$ is a finite $n{r}-1$
dimension subspace of $H_{0}^{1}(0,1)$ and, following a Galerkin approach [4],
we approximate the solution $u$ of the variational problem by solving the
problem: Find $u_{r,n}\in W_{n}^{(r)}$ such that

(32) $a(u_{r,n},v)=\langle\psi,v\rangle,\quad\forall v\in W_{n}^{(r)}.$

We define the uniform knot sequence

(33) $\xi_{i}=\frac{i}{nr},\quad i=0,\dots,nr,$

and the Lagrangian basis functions by
$\phi_{j}^{n,r}(\xi_{i})=\delta_{i,j},\,i,j=0,\dots,nr,$ with $\delta_{i,j}$
being the Kronecker delta. It is well known that the latter definition is
well-posed and that $\\{\phi_{1}^{n,r},\dots,\phi_{nr-1}^{n,r}\\}$ is a basis
for $W_{n}^{(r)}$. Then $u_{r,n}$ can be written as a linear combination of
such basis as $u_{r,n}=\sum_{j=1}^{nr-1}u_{j}\phi_{j}^{n,r}{.}$ Using this
discretization, approximately solving the problem (32) reduces to the solution
of the linear system $K_{n}^{(r)}\textbf{u}=\textbf{b},$ with

$K_{n}^{(r)}=[a(\phi_{j}^{n,r},\phi_{i}^{n,r})]_{i,j=1}^{nr-1},\quad\textbf{b}=\left[\langle\psi,\phi_{i}^{n,r}\rangle\right]_{i=1}^{nr-1},\quad\textbf{u}=\left[u_{i}\right]_{i=1}^{nr-1}.$

The spectral properties of the stiffness matrix-sequence
$\\{K_{n}^{(r)}\\}_{n}$ were studied in [18]. In the following we report the
spectral properties of matrix-valued function $\mathbf{f}$ associated with the
normalized matrix-sequence
$\\{T_{n}(\mathbf{f})\\}_{n}=\\{nK_{n}^{(r)}\\}_{n},$ which are needed for our
analysis [18, 27].

######  Theorem 5.1.

The $r\times r$ matrix-valued generating function of
$\\{T_{n}(\mathbf{f})\\}_{n}=\\{nK_{n}^{(r)}\\}_{n}$ is

(34) $\displaystyle\mathbf{f}_{\mathbb{Q}_{r}}(\theta)=a_{0}+a_{1}{\rm
e}^{\imath\theta}+a_{1}^{T}{\rm e}^{-\imath\theta}$

and the following statements hold true:

  1. 1.

$\mathbf{f}_{\mathbb{Q}_{r}}(0){\rm e}_{r}=0$, ${\rm e}_{r}$ vector of all
ones, $r\geq 1$;

  2. 2.

there exist constants $C_{2}\geq C_{1}>0$ (dependent on $f_{\mathbb{Q}_{r}}$)
such that

(35)
$C_{1}(2-2\cos(\theta))\leq\lambda_{1}(\mathbf{f}_{\mathbb{Q}_{r}}(\theta))\leq
C_{2}(2-2\cos(\theta));$

and

  3. 3.

there exist constants $M_{2}\geq M_{1}>0$ (dependent on
$\mathbf{f}_{\mathbb{Q}_{r}}$) such that

(36)
$0<{M_{1}}\leq\lambda_{j}(\mathbf{f}_{\mathbb{Q}_{r}}(\theta))\leq{M_{2}},\ \
\ \ j=2,\ldots,r.$

From the latter result, we have that $\mathbf{f}_{\mathbb{Q}_{r}}$ is a
matrix-valued trigonometric polynomial which fulfills the hypotheses of
Subsection 4. Indeed, for each $r\geq 1$ we have that

  * •

the minimum eigenvalue function $\lambda_{\min}(\mathbf{f}_{\mathbb{Q}_{r}})$
of $\mathbf{f}_{\mathbb{Q}_{r}}$ has a zero of order 2 in $\theta_{0}=0$;

  * •

for $j=2,\dots,r$, it holds
$\lambda_{j}(\mathbf{f}_{\mathbb{Q}_{r}}(\theta))>0$, for all
$\theta\in[0,2\pi]$.

Then, the first item of Theorem 5.1 implies that $\mathbf{f}_{\mathbb{Q}_{r}}$
can be decomposed as in equation (6), with $q_{\bar{\jmath}}=q_{1}$ equal to
${\rm e}_{r}$, the column vector of all ones.

Consequently, in next section we test the applicability of the results given
in the Section 4, and we confirm that two standard projectors are effective in
terms of convergence and optimality when used for solving the linear system
which has $T_{n}(\mathbf{f}_{\mathbb{Q}_{r}})$ as coefficient matrix. In
particular, we will deal with projector of the form

$P_{n,k}^{{}_{\mathbb{Q}_{r}}}=T_{n}(\mathbf{p}_{{}_{\mathbb{Q}_{r}}})(K_{n,k}^{Even}\otimes
I_{d}),$

where its properties and efficiency will depend on those of the associated
trigonometric polynomial $\mathbf{p}_{{}_{\mathbb{Q}_{r}}}$.

###  5.2 The scalar linear interpolation projector

The discretization using $\mathbb{Q}_{r}$ Lagrangian finite elements provides
an approximate solution at all nodes used as interpolation points within an
element and on its boundaries. While the use of linear interpolation is common
in finite difference discretizations of partial differential equations [34],
it can be used in this setting, as well. For $n$ elements and using polynomial
degree $r$ it can be written as

(37) $P_{n,k}^{{r}}=T_{rn}(2+2\cos(\theta))K^{Even}_{rn,\frac{r(n-1)}{2}}.$

We will now show that this scalar interpolation nevertheless satisfies the
hypotheses of Lemma 4.4. For that purpose we have to show that it fits into
the block setting of the present paper. Hence, first we have to rewrite
$P_{n,k}^{r}$ in block form as

(38) $P_{n,k}^{{r}}=T_{n}(\mathbf{p}_{{}_{L_{r}}})(K^{Even}_{n,k}\otimes
I_{r}).$

which means that we want to find a matrix-valued trigonometric polynomial
$\mathbf{p}_{{}_{L_{r}}}$ such that the latter equation is true, with
$P_{n,k}^{{r}}$ defined as in (37).

Recalling the action of the cutting matrix $(K^{Even}_{n,k}\otimes I_{r})$,
seen in Subsection 3.2, we observe that $P_{n,k}^{{r}}$ can be rewritten in
the desired block form with associated matrix-valued trigonometric polynomial
$\mathbf{p}_{{}_{L_{r}}}$ of the form

(39) $\mathbf{p}_{{}_{L_{r}}}(\theta)=\hat{a}_{0}+\hat{a}_{-1}{\rm
e}^{-\imath\theta}+\hat{a}_{1}{\rm e}^{\imath\theta},$

where the expression of the Fourier coefficients
$\hat{a}_{0},\hat{a}_{-1},\hat{a}_{1}$ depends on whether the degree is even
or odd. Indeed, we have

  1. 1.

In the case of even degree $r$, we define

$A_{1}=T_{r}(2+2\cos(\theta))K^{Even}_{r,\frac{r}{2}}=\begin{bmatrix}1&&&&\\\
2&&&&\\\ 1&1&&&\\\ &2&&&\\\ &1&&&\\\ &&\ddots&&\\\ &&&1&\\\ &&&2&\\\ &&&1&1\\\
&&&&2\end{bmatrix}\in\mathbb{R}^{r\times\frac{r}{2}}.$

Then the identity (38) holds with

$\displaystyle\hat{a}_{-1}$
$\displaystyle=\begin{bmatrix}&A_{1}&|&\textbf{0}_{{r,\frac{r}{2}}}&\end{bmatrix},\quad\hat{a}_{0}=\left[\begin{array}[]{ccc|c|c}&\textbf{0}_{1,\frac{r}{2}-1}&&1&\\\
\cline{1-4}\cr&&&&A_{1}\\\
&\textbf{0}_{{r}-1,\frac{r}{2}-1}&&\textbf{0}^{T}_{1,\frac{r}{2}-1}&\end{array}\right],$
$\displaystyle\hat{a}_{1}$
$\displaystyle=\left[\begin{array}[]{ccc|c}&\textbf{0}_{1,r-1}&&1\\\
\cline{1-4}\cr&&&\\\
&\textbf{0}_{r-1,r-1}&&\textbf{0}^{T}_{r-1}\end{array}\right].$

Note that

(40) $\sum_{j=1}^{\frac{r}{2}}[A_{1}]_{1,j}=1\quad\text{ and
}\quad\sum_{j=1}^{\frac{r}{2}}[A_{1}]_{i,j}=2,\,\text{ for $i=2,\dots,r$.}$

  2. 2.

In the case of odd degree $r$ we define

$\displaystyle A_{2}=T_{r}(2+2\cos(\theta))K^{Odd}_{r,\frac{r+1}{2}}$
$\displaystyle=\begin{bmatrix}2&&&&\\\ 1&1&&&\\\ &2&&&\\\ &1&&&\\\
&&\ddots&&\\\ &&&1&\\\ &&&2&\\\ &&&1&1\\\
&&&&2\end{bmatrix}\in\mathbb{R}^{r\times\frac{r+1}{2}},$ $\displaystyle
A_{3}=T_{r}(2+2\cos(\theta))K^{Even}_{r,\frac{r+1}{2}}$
$\displaystyle=\begin{bmatrix}1&&&&\\\ 2&&&&\\\ 1&1&&&\\\ &2&&&\\\ &1&&&\\\
&&\ddots&&\\\ &&&1&\\\ &&&2&\\\
&&&1&1\end{bmatrix}\in\mathbb{R}^{r\times\frac{r+1}{2}}.$

Then (38) holds with

$\displaystyle\hat{a}_{-1}$
$\displaystyle=\begin{bmatrix}A_{3}&|&\textbf{0}_{r,\frac{r-1}{2}}&\end{bmatrix},$
$\displaystyle\hat{a}_{0}$
$\displaystyle=\begin{bmatrix}&\textbf{0}_{r,\frac{r-1}{2}}&|&A_{2}&\end{bmatrix},$
$\displaystyle\hat{a}_{1}$
$\displaystyle=\left[\begin{array}[]{ccc|c}&\textbf{0}_{1,r-1}&&1\\\
\cline{1-4}\cr&&&\\\
&\textbf{0}_{r-1,r-1}&&\textbf{0}^{T}_{r-1}\end{array}\right].$

Further we have

(41)
$\sum_{j=1}^{\frac{r+1}{2}}[A_{2}]_{1,j}=2,\,\sum_{j=1}^{\frac{r+1}{2}}[A_{3}]_{1,j}=1\,\text{
and
}\,\sum_{j=1}^{\frac{r+1}{2}}[A_{2}]_{i,j}=\sum_{j=1}^{\frac{r+1}{2}}[A_{3}]_{i,j}=2\text{
for $i=2,\dots,r$.}$

In the following we show that $\mathbf{p}_{{}_{L_{r}}}$ satisfies the
hypotheses of the Lemma 4.4.

######  Lemma 5.2.

Let $\mathbf{p}_{{}_{L_{r}}}$ be the $r\times r$ trigonometric polynomial
defined in (39), and ${\rm e}_{r}=[1,\dots,1]^{T}\in\mathbb{R}^{r}$. Then,

  1. 1)

$\mathbf{p}_{{}_{L_{r}}}(0)\,{\rm e}_{r}=4\,{\rm e}_{r}$.

  2. 2)

$\mathbf{p}_{{}_{L_{r}}}(\pi)\,{\rm e}_{r}=0\,{\rm e}_{r}$.

  3. 3)

$\mathbf{p}_{{}_{L_{r}}}(0)^{H}\,{\rm e}_{r}=4\,{\rm e}_{r}$.

######  Proof 5.3.

The first two items are equivalent to require that the sum of the elements in
each row of the matrices $\mathbf{p}_{{}_{L_{r}}}(0)$ and
$\mathbf{p}_{{}_{L_{r}}}(\pi)$ is $4$ and $0$, respectively. Hence, to prove
$1)$, it is sufficient to show that

$\sum_{j=1}^{r}[\mathbf{p}_{{}_{L_{r}}}(0)]_{i,j}=\sum_{j=1}^{r}[\hat{a}_{0}+\hat{a}_{1}+\hat{a}_{-1}]_{i,j}=4,\quad
i=1,\dots,r.$

Then, we can exploit the structure of the Fourier coefficients
$\hat{a}_{-1},\hat{a}_{1},\hat{a}_{0}$ for even and odd degree. In particular,
looking at the structure of the matrices $A_{1}$, $A_{2}$, $A_{3}$ and at
relations (40) and (41), we have that for even degree $r$

$\begin{split}&\sum_{j=1}^{r}[\mathbf{p}_{{}_{L_{r}}}(0)]_{i,j}=\begin{cases}1+\left(2\sum_{j=1}^{\frac{r}{2}}[A_{1}]_{1,j}\right)+1=4,&{\rm
for}\,i=1\\\ \left(2\sum_{j=1}^{\frac{r}{2}}[A_{1}]_{i,j}\right)=4,&{\rm
for}\,i=2,\dots,r\\\ \end{cases},\end{split}$

and for odd degree $r$

$\begin{split}&\sum_{j=1}^{r}[\mathbf{p}_{{}_{L_{r}}}(0)]_{i,j}\\!=\begin{cases}\left(\sum_{j=1}^{\frac{r+1}{2}}[A_{3}]_{1,j}\\!+\\![A_{2}]_{1,j}\right)\\!+\\!1\\!=\\!4,&{\rm
for}\,i\\!=\\!1\\\
\left(\sum_{j=1}^{\frac{r}{2}}[A_{3}]_{i,j}\\!+\\![A_{2}]_{i,j}\right)\\!=\\!4,&{\rm
for}\,i\\!=\\!2,\dots,r\end{cases}\\!.\end{split}$

The proof of $2)$ can be repeated following the idea in $1)$ and noting that

$\mathbf{p}_{{}_{L_{r}}}(\pi)=\hat{a}_{0}-\hat{a}_{1}-\hat{a}_{-1}.$

Analogously, the third item can be proven following the same idea of $1)$,
showing that the sum of the elements in each column of the matrices
$\mathbf{p}_{{}_{L_{r}}}(0)$ is $4$. Since it is a straightforward
computation, we omit the details.

The latter result, together with Lemma 4.4 permits to conclude that
$\mathbf{p}_{{}_{L_{r}}}$ satisfies condition $(ii)$, once that we prove that
it satisfies the condition $(i)$, so that the matrix-valued function s is
well-defined. By direct computation, we find that for both even and odd $r$ we
have

$\mathbf{p}_{{}_{L_{r}}}(\theta)^{H}\mathbf{p}_{{}_{L_{r}}}(\theta)+\mathbf{p}_{{}_{L_{r}}}(\theta+\pi)^{H}\mathbf{p}_{{}_{L_{r}}}(\theta+\pi)=\begin{bmatrix}12&2&0&\dots&2{\rm
e}^{2\imath\theta}\\\ 2&12&2&\dots&0\\\ &&\ddots&\\\ 0&&&12&2\\\ 2{\rm
e}^{-2\imath\theta}&0&\dots&2&12\end{bmatrix},$

which is clearly a definite positive matrix for all $\theta\in[0,2\pi)$, so
$\mathbf{p}_{{}_{L_{r}}}$ satisfies condition $(i)$. Then, the function
$\textbf{s}(\theta)$ defined in (7) is well-defined.

The validation of condition $(iii)$ will be investigated in subsection 5.4
since we will treat it for both the projector associated with
$\mathbf{p}_{{}_{L_{r}}}$ and the classical geometric projector described in
the next subsection.

###  5.3 The projector using the finite element basis functions

In the present subsection we deal with the projector which is constructed
following the classical approach used for finite elements [4]. It has been
already treated for the $\mathbb{Q}_{r}$ Lagrangian FEM stiffness matrices in
the algebraic multigrid setting. Indeed, in [14] the authors proved the
optimality of the TGM methods for $r=2,3$. Our goal is to generalize the study
of the multigrid method procedure, proving that the restriction matrix can be
written for any degree $r$ in the form

(42) $P_{n,k}^{{r}}=T_{n}(\mathbf{p}_{{}_{G_{r}}})(K_{n,k}^{Even}\otimes
I_{d}),$

with $\mathbf{p}_{{}_{G_{r}}}$ being a matrix-valued trigonometric polynomial
that satisfies the hypotheses of Lemma 4.4, and then those of Theorem 4.1.

Let us start fixing the $r$ and taking as first $n=2$. Then we have from (33)
the knot sequence $\xi_{i}^{2r}=\frac{i}{2r},\,i=0,\dots,2r.$ If we take $n=4$
the uniform knot sequence is $\xi_{i}^{4r}=\frac{i}{4r},\,i=0,\dots,4r,$ and
thus it can be obtained from $\\{\xi_{i}^{2r}\\}_{i}$ adding the midpoint of
each sub interval defined by the points in $\\{\xi_{i}^{2r}\\}_{i}$.

Taking the Lagrangian basis functions for the spaces $W_{2}^{r}$ and
$W_{4}^{r}$, defined in Subsection 5.1, the latter observation implies that

(43) $W_{2}^{r}\subseteq W_{4}^{r}.$

The geometric multigrid strategy suggests to construct a prolongation operator
$\mathcal{P}~{}:~{}W_{2}^{r}\rightarrow W_{4}^{r}$, imposing
$\mathcal{P}v^{2,r}=v^{2,r},$ $\forall v^{2,r}\in W_{2}^{r}.$ A basis function
$\phi_{j}^{2,r}$ can be then written as a linear combination of the functions
$\phi_{j}^{4,r}$, that is
$\phi_{j}^{2,r}(x)=\sum_{i=1}^{4r-1}c_{i}\phi_{i}^{4,r}(x).$ From the
properties of the basis functions, we have that
$\phi_{j}^{4,r}(\xi_{i})=r_{i,j}$. Consequently, for $i=1,\dots,4r-1$, the
coefficients $c_{i}$ are given by the evaluations of
$\phi_{j}^{2,r}(\xi_{i})$, and this implies that
$\phi_{j}^{2,r}(x)=\sum_{i=1}^{4r-1}\phi_{j}^{2,r}(\xi_{i})\phi_{i}^{4,r}(x).$
Therefore, the $j-th$ column $({P})_{j}$ of the matrix $P$ representing the
prolongation operator $\mathcal{P}$ is given by

(44) $({P})_{j}=[\phi_{j}^{2,r}(\xi_{i})]_{i=1}^{4r-1}.$

Since we are in the setting of multigrid methods for $r\times r$ block-
Toeplitz matrices, from Subsection 3.2 we have that $n$ is taken of the form
$2^{t}-1$, $k=\frac{n-1}{2}$ and we look for a prolongation matrix of the form
(42). Taking inspiration from [14], we define the matrix-valued trigonometric
polynomial $\mathbf{p}_{{}_{G_{r}}}$ by

(45) $\mathbf{p}_{{}_{G_{r}}}(\theta)=\hat{b}_{0}+\hat{b}_{1}{\rm
e}^{\iota\theta}+\hat{b}_{-1}{\rm e}^{-\iota\theta}+\hat{b}_{2}{\rm
e}^{2\iota\theta}+\hat{b}_{-2}{\rm e}^{-2\iota\theta}$

with $\hat{b}_{-2}=0_{r\times
r},\,\hat{b}_{-1}=[P_{i,j}]_{\begin{subarray}{c}i=1,\dots,r\\\
j=1,\dots,r\end{subarray}},\,\hat{b}_{0}=[P_{i,j}]_{\begin{subarray}{c}i=r+1,\dots,2r\\\
j=1,\dots,r\end{subarray}},\,\hat{b}_{1}=[P_{i,j}]_{\begin{subarray}{c}i=2r+1,\dots,3r\\\
j=1,\dots,r\end{subarray}},\,$ and
$\hat{b}_{2}=[P_{i,j}]_{\begin{subarray}{c}i=3r+1,\dots,4r\\\
j=1,\dots,r\end{subarray}}.$ Then, from the expression of the columns of the
matrix $P$ in (44), we have

$\displaystyle\hat{b}_{-1}=\begin{bmatrix}\phi_{1}^{2,r}(\xi_{1}^{4,r})&\dots&\phi_{{\rm
r}}^{2,r}(\xi_{1}^{4,r})\\\ \vdots&&\vdots\\\
\phi_{1}^{2,r}(\xi_{r}^{4,r})&\dots&\phi_{{\rm r}}^{2,r}(\xi_{r}^{4,r})\\\
\end{bmatrix},\quad$
$\displaystyle\hat{b}_{0}=\begin{bmatrix}\phi_{1}^{2,r}(\xi_{r+1}^{4,r})&\dots&\phi_{{\rm
r}}^{2,r}(\xi_{r+1}^{4,r})\\\ \vdots&&\vdots\\\
\phi_{1}^{2,r}(\xi_{2r}^{4,r})&\dots&\phi_{{\rm r}}^{2,r}(\xi_{2r}^{4,r})\\\
\end{bmatrix},$ $\displaystyle\hat{b}_{1}=\begin{bmatrix}0&\dots&0&\phi_{{\rm
r}}^{2,r}(\xi_{2r+1}^{4,r})\\\ \vdots&&\vdots&\vdots\\\ 0&\dots&0&\phi_{{\rm
r}}^{2,r}(\xi_{3r}^{4,r})\\\ \end{bmatrix},\quad$
$\displaystyle\hat{b}_{2}=\begin{bmatrix}0&\dots&0&\phi_{{\rm
r}}^{2,r}(\xi_{3r+1}^{4,r})\\\ \vdots&&\vdots&\vdots\\\ 0&\dots&0&\phi_{{\rm
r}}^{2,r}(\xi_{4r}^{4,r})\\\ \end{bmatrix}.$

where, for the expressions of $\hat{b}_{1}$ and $\hat{b}_{2}$, we are using
the fact that the sets ${\rm supp}(\phi_{1}^{2,r}),\dots,{\rm
supp}(\phi_{r-1}^{2,r})$ are included in $[0,\xi_{2r}^{4,r}]$, see [18, pag
1108]. Moreover, from [18, Equation (3.5)] we can also see that, for
$i=2r+1,\dots,4r-1$,

$\phi_{r}^{2,r}(\xi_{i}^{4,r})=\phi_{0}^{2,r}\left(\xi_{i}^{4,r}-\frac{1}{2}\right)=\phi_{0}^{2,r}(\xi_{i-2r}^{4,r}),$

hence we have

(46)
$\begin{split}\hat{b}_{1}=\begin{bmatrix}0&\dots&0&\phi_{0}^{2,r}(\xi_{1}^{4,r})\\\
\vdots&&\vdots&\vdots\\\ 0&\dots&0&\phi_{0}^{2,r}(\xi_{r}^{4,r})\\\
\end{bmatrix}\quad{\rm
and}\quad\hat{b}_{2}=\begin{bmatrix}0&\dots&0&\phi_{0}^{2,r}(\xi_{r+1}^{4,r})\\\
\vdots&&\vdots&\vdots\\\ 0&\dots&0&\phi_{0}^{2,r}(\xi_{2r}^{4,r})\\\
\end{bmatrix}.\\\ \end{split}$

We want to prove that such projector $P^{{r}}_{n,k}$ satisfies the hypothesis
of Lemma 4.4. Since, from Theorem 5.1, we know that ${\rm
e}_{r}=[1,\dots,1]^{T}\in\mathbb{R}^{r}$ is the eigenvector of $\mathbf{f}(0)$
associated with the ill-conditioned subspace, the next lemma gives us the
proof that $P^{{r}}_{n,k}$ satisfies the hypothesis of Theorem 4.1.

######  Lemma 5.4.

Let $\mathbf{p}_{{}_{G_{r}}}$ be the $r\times r$ trigonometric polynomial
defined in (45), and ${\rm e}_{r}=[1,\dots,1]^{T}\in\mathbb{R}^{r}$. Then

  1. 1)

$\mathbf{p}_{{}_{G_{r}}}(0)\,{\rm e}_{r}=2\,{\rm e}_{r}$,

  2. 2)

$\mathbf{p}_{{}_{G_{r}}}(\pi)\,{\rm e}_{r}=0\,{\rm e}_{r}$,

  3. 3)

$\mathbf{p}_{{}_{G_{r}}}(0)$ is non-singular.

######  Proof 5.5.

Note that the thesis is equivalent to require that the sum of the elements in
each row of the matrices $\mathbf{p}_{{}_{G_{r}}}(0)$ and
$\mathbf{p}_{{}_{G_{r}}}(\pi)$ is $2$ and $0$, respectively. Then, to prove
item $1)$, we prove that for every $i=1,\dots,r$
$\sum_{j=1}^{r}[\mathbf{p}_{{}_{G_{r}}}(0)]_{i,j}=2.$ The expression of
$\mathbf{p}_{{}_{G_{r}}}(\theta)$ in (45) yields
$\mathbf{p}_{{}_{G_{r}}}(0)=\hat{b}_{0}+\hat{b}_{1}+\hat{b}_{-1}+\hat{b}_{2},$
then we have for $i=1,\dots,r$

(47)
$\begin{split}&\sum_{j=1}^{r}[\mathbf{p}_{{}_{G_{r}}}(0)]_{i,j}=\sum_{j=1}^{r}[\hat{b}_{0}+\hat{b}_{1}+\hat{b}_{-1}+\hat{b}_{2}]_{i,j}=\\\
&\left(\sum_{j=1}^{r}\phi_{j}^{2,r}(\xi_{i+r}^{4,r})\right)+\phi_{0}^{2,r}(\xi_{i}^{4,r})+\left(\sum_{j=1}^{r}\phi_{j}^{2,r}(\xi_{i}^{4,r})\right)+\phi_{0}^{2,r}(\xi_{i+r}^{4,r})\end{split}.$

From the fact that the basis functions form a partition of the unity and since
${\rm supp}(\phi_{j}^{2,r})\cap[0,\xi^{4,r}_{2r}]=\emptyset$,
$j=r+1,\dots,2r,$ we have, for $i=1,\dots,r$, that

$\sum_{j=1}^{r}[\mathbf{p}_{{}_{G_{r}}}(0)]_{i,j}=\left(\sum_{j=0}^{2r}\phi_{j}^{2,r}(\xi_{i}^{4,r})\right)+\left(\sum_{j=0}^{2r}\phi_{j}^{2,r}(\xi_{i+r}^{4,r})\right)=2.$

In order to prove item $2)$ we write analogously
$\mathbf{p}_{{}_{G_{r}}}(\pi)=\hat{b}_{0}-\hat{b}_{1}-\hat{b}_{-1}+\hat{b}_{2},$
and, for $i=1,\dots,r$,

$\begin{split}&\sum_{j=1}^{r}[\mathbf{p}_{{}_{G_{r}}}(\pi)]_{i,j}=\sum_{j=1}^{r}[\hat{b}_{0}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}+}\hat{b}_{1}-\hat{b}_{-1}+\hat{b}_{2}]_{i,j}=\\\
&\left(\sum_{j=0}^{2r}\phi_{j}^{2,r}(\xi_{i}^{4,r})\right)-\left(\sum_{j=0}^{2r}\phi_{j}^{2,r}(\xi_{i+r}^{4,r})\right)=0.\end{split}$

The item $3)$ is equivalent to ${\rm
det}\,\left(\mathbf{p}_{{}_{G_{r}}}(0)\right)\neq 0$. By direct computation,
we have that

${\rm det}\,\left(\mathbf{p}_{{}_{G_{r}}}(\theta)\right)=\frac{{\rm
e}^{-r\iota\theta}({\rm e}^{\iota\theta}+1)^{r+1}}{2^{\frac{r(r+1)}{2}}}.$

Finally, since ${\rm e}^{-r\iota\theta}\neq 0$, $\forall\theta\in[0,2\pi]$ and
$({\rm e}^{\iota\theta}+1)=0$ only if $\theta=\pi+2\ell\pi$, we have that

${\rm det}\,\left(\mathbf{p}_{{}_{G_{r}}}(\theta)\right)\neq 0,\quad{\rm
for}\quad\theta\in[0,2\pi]\setminus\\{\pi\\},$

hence $\mathbf{p}_{{}_{G_{r}}}(0)$ is non-singular.

Once we verify that $\mathbf{p}_{{}_{G_{r}}}$ satisfies condition $(i)$, we
can use Lemmas 5.4 and 4.6 to conclude that the matrix-valued function s is
well-defined and $\mathbf{p}_{{}_{G_{r}}}$ satisfies condition $(ii)$. To
prove that
$\mathbf{p}_{{}_{G_{r}}}(\theta)^{H}\mathbf{p}_{{}_{G_{r}}}(\theta)+\mathbf{p}_{{}_{G_{r}}}(\theta+\pi)^{H}\mathbf{p}_{{}_{G_{r}}}(\theta+\pi)>0$
it is sufficient to show that both ${\rm
det}\,(\mathbf{p}_{{}_{G_{r}}}(\theta)^{H}\mathbf{p}_{{}_{G_{r}}}(\theta))$
and ${\rm
det}\,(\mathbf{p}_{{}_{G_{r}}}(\theta+\pi)^{H}\mathbf{p}_{{}_{G_{r}}}(\theta+\pi))$
are non-negative definite matrix-valued functions which are singular
respectively in $\theta_{1}$ and $\theta_{2}$, with
$\theta_{1}\neq\theta_{2}.$ Indeed, we have that

${\rm
det}\,\left(\mathbf{p}_{{}_{G_{r}}}(\theta)^{H}\mathbf{p}_{{}_{G_{r}}}(\theta)\right)={\rm
det}\,(\mathbf{p}_{{}_{G_{r}}}(\theta))^{2}=\frac{{\rm
e}^{-2r\iota\theta}({\rm e}^{\iota\theta}+1)^{2(r+1)}}{2^{r(r+1)}},$

which is zero for $\theta_{1}=\pi.$ Analogously, it holds

$\begin{split}&{\rm
det}\,\left(\mathbf{p}_{{}_{G_{r}}}(\theta+\pi)^{H}\mathbf{p}_{{}_{G_{r}}}(\theta+\pi)\right)=\\\
&{\rm
det}\,\left(\mathbf{p}_{{}_{G_{r}}}(\theta+\pi)\right)^{2}=\left(\frac{{\rm
e}^{-r\iota(\theta+\pi)}({\rm
e}^{\iota(\theta+\pi)}+1)^{r+1}}{2^{\frac{r(r+1)}{2}}}\right)^{2}=\frac{{\rm
e}^{-2r\iota\theta}({\rm
e}^{\iota\theta}-1)^{2(r+1)}}{2^{r(r+1)}},\end{split}$

which is zero for $\theta_{2}=0.$

###  5.4 Optimal convergence of the V-cycle using the projector
$P_{n,k}^{{}_{\mathbb{Q}_{r}}}$

For both projectors described in Subsections 5.2 and 5.3 we have to verify the
limit condition (iii), in order to theoretically ensure the TGM optimality.

For this purpose it is sufficient to show either that the function
$1-\lambda_{\bar{\jmath}}(\textbf{s}(\theta))$ has a zero at least of the same
order of $\lambda_{\bar{\jmath}}(\mathbf{f}_{\mathbb{Q}_{r}}(\theta))$, or,
using the result in Lemma 4.9, that this property is satisfied by the
eigenvalue function
$\lambda_{\bar{\jmath}}(\mathbf{p}_{{}_{G_{r}}}(\theta+\pi))^{2}$.

  1. 1.

For the linear interpolation operator:

     * •

for even degree, we have that $\textbf{s}(\theta)$ is a projector since it can
be easily verified that
$\textbf{s}^{2}(\theta)-\textbf{s}(\theta)=\textbf{0}_{r\times r}$. Hence,
from condition (ii), we have $\lambda_{\bar{\jmath}}(\textbf{s}(0))=1$, and,
from the continuity of the eigenvalue functions (Lemma 3.1), we have that
$\lambda_{\bar{\jmath}}(\textbf{s}(\theta))\equiv 1$. Hence, it is
straightforward to see that the condition (iii) is verified;

     * •

for odd degree, it can be numerically proved that
$\lambda_{\bar{\jmath}}(\mathbf{p}_{{}_{L_{r}}}(\theta+\pi))^{2}$ has a zero
of order $4$ in $0$, then condition (iii) is verified. For this purpose, we
can numerically study the behavior of the function
$\det(\mathbf{p}_{{}_{L_{r}}}(\theta+\pi)\mathbf{p}_{{}_{L_{r}}}(\theta+\pi)^{H})$.
Indeed, since for $l=2,\dots,r,\,\theta\in[0,2\pi],$

(48)
$\lambda_{\bar{\jmath}}\left(\mathbf{p}_{{}_{L_{r}}}(\theta+\pi)\mathbf{p}_{{}_{L_{r}}}(\theta+\pi)^{H}\right)<\lambda_{l}\left(\mathbf{p}_{{}_{L_{r}}}(\theta+\pi)\mathbf{p}_{{}_{L_{r}}}(\theta+\pi)^{H}\right),$

the behaviour of
$\lambda_{\bar{\jmath}}(\mathbf{p}_{{}_{L_{r}}}(\theta+\pi)\mathbf{p}_{{}_{L_{r}}}(\theta+\pi)^{H})$
in $0$ is equivalent to that of
$\det\left(\mathbf{p}_{{}_{L_{{r}}}}(\theta+\pi)\mathbf{p}_{{}_{L_{{r}}}}(\theta+\pi)^{H}\right)=\prod_{i=1}^{r}\lambda_{l}\left(\mathbf{p}_{{}_{L_{{r}}}}(\theta+\pi)\mathbf{p}_{{}_{L_{{r}}}}(\theta+\pi)^{H}\right)$
at the same point, which as a product of nonnegative functions is still a
nonnegative function. We numerically checked that

$\displaystyle\det\left(\mathbf{p}_{{}_{L_{{r}}}}(\theta+\pi)\mathbf{p}_{{}_{L_{{r}}}}(\theta+\pi)^{H}\right)={\rm
e}^{-2\iota\theta}({\rm e}^{\iota\theta}-1)^{4},$

which has a zero of order $4$ in $0$.

  2. 2.

For the geometric projector operator we consider the even and odd degree $r$
simultaneously and we follow the latter strategy of studying the behavior of
$\det\left(\mathbf{p}_{{}_{G_{{r}}}}(\theta+\pi)\mathbf{p}_{{}_{G_{{r}}}}(\theta+\pi)^{H}\right)$
in $0$. From the proof of item 3) of Lemma 5.4 we have that

$\displaystyle\det\left(\mathbf{p}_{{}_{G_{{r}}}}(\theta+\pi)\mathbf{p}_{{}_{G_{{r}}}}(\theta+\pi)^{H}\right)=\frac{{\rm
e}^{-2r\iota\theta}({\rm e}^{\iota\theta}-1)^{2(r+1)}}{2^{r(r+1)}},$

which clearly has a zero of order $2(r+1)$ in $0$.

###  5.5 Example $r=2$

We conclude the section with the application of the results in Section 4.1 and
Subsection 4.2 on the scalar linear interpolation projector for the specific
case $r=2$ for the problem

$\left\\{\begin{array}[]{ll}-(a(x)u(x)^{\prime})^{\prime}=\psi(x),\,{\rm
on}\,(0,1)\\\ u(0)=u(1)=0,\end{array}\right.$

which is the variable coefficient version of the problem in (30). In this
setting the grid transfer operator $P_{n,k}^{{2}}$ is a $2n\times n-1$ matrix
given by

(49) $P_{n,k}^{{2}}=T_{n}(\mathbf{p}_{{}_{L_{2}}})(K^{Even}_{n,k}\otimes
I_{2}).$

with matrix-valued trigonometric polynomial
$\mathbf{p}_{{}_{L_{2}}}(\theta)=\begin{bmatrix}1+{\rm e}^{-\iota\theta}&{\rm
e}^{\iota\theta}+1\\\ 2{\rm e}^{-\iota\theta}&2\end{bmatrix}.$ The cut
stiffness matrix $[T_{n}(\mathbf{\textbf{f}}_{\mathbb{Q}_{2}})]_{-},$ has the
associated generating function

$\begin{split}\mathbf{f}_{\mathbb{Q}_{2}}(\theta)=&\frac{1}{3}\left(\begin{bmatrix}16&-8\\\
-8&14\end{bmatrix}+\begin{bmatrix}0&-8\\\ 0&1\end{bmatrix}{\rm
e}^{\iota\theta}+\begin{bmatrix}0&0\\\ -8&1\end{bmatrix}{\rm
e}^{-{\iota}\theta}\right)=\\\ &\frac{1}{3}\begin{bmatrix}16&-8(1+{\rm
e}^{\iota\theta})\\\ -8(1+{\rm e}^{-\iota\theta})&14+{\rm
e}^{\iota\theta}+{\rm e}^{-\iota\theta}\end{bmatrix},\end{split}$

with the following properties:

  * •

$\lambda_{1}(\mathbf{\textbf{f}}_{\mathbb{Q}_{2}}(\theta))$ has a zero of
order 2 in $\theta_{0}=0$.

  * •

$\mathbf{\textbf{f}}_{\mathbb{Q}_{{2}}}(0)q_{1}(0)=0$, $q_{1}(0)=[1,1]^{T}$.

By direct computation it is possible to check that the trigonometric
polynomial $\mathbf{p}_{{}_{L_{2}}}$ verifies

  * •

$\left.\mathbf{p}_{{}_{L_{2}}}(\theta)^{H}\mathbf{p}_{{}_{L_{2}}}(\theta)+\mathbf{p}_{{}_{L_{2}}}(\theta+\pi)^{H}\mathbf{p}_{{}_{L_{2}}}(\theta+\pi)=\begin{bmatrix}12&2\\\
2&12\end{bmatrix}>0.\quad\right\\}\Rightarrow{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\,(i)}$

  * •

$\left.\begin{tabular}[]{@{}c@{}}$\mathbf{\textbf{p}}^{(2)}(0)\,{\rm
e}_{2}=\begin{bmatrix}2&2\\\ 2&2\end{bmatrix}e_{2}=4\,{\rm e}_{2}$\\\
$\mathbf{\textbf{p}}^{(2)}(\pi)\,{\rm e}_{2}=\begin{bmatrix}0&0\\\
-2&2\end{bmatrix}e_{2}=0\,{\rm e}_{2}$\\\
$\,\mathbf{\textbf{p}}^{(2)}(0)^{H}\,{\rm e}_{2}=\begin{bmatrix}2&2\\\
2&2\end{bmatrix}e_{2}=4\,{\rm e}_{2}$\\\
\end{tabular}\qquad\qquad\qquad\qquad\qquad\qquad\quad\right\\}\Rightarrow{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\,(ii)}$

  * •

$\lambda_{1}(\mathbf{\textbf{p}}^{(2)}(\theta+\pi))=0.$
$\qquad\quad\quad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\left.\right\\}\Rightarrow{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}(\ref{eq:final_bound_vcycle})}$

In particular, the second, third and fourth conditions are the hypotheses of
Lemma 4.4 needed for the validation of $(ii)$. The fact that the minimum
eigenvalue function of $\mathbf{\textbf{p}}^{(2)}(\theta+\pi)$ is identically
zero implies the thesis of Lemma 4.13. Hence, the convergence and optimality
of the V-cycle method is ensured when applied to the problem (30) using
$P_{n,k}^{{2}}$. This is reflected on the fact that the number of iterations
needed to reach the convergence of the methods is constant when increasing the
problem size. In Table 1 we show the results for the cases
$a(x)=1,x^{2}+1,{\rm e}^{x}-2x$, using as pre and post smoother 1 iteration of
the Gauss-Seidel method. We highlight that also other smoothers are suitable
for the optimality of the method. For instance, Lemma 2.2 guarantees that the
relaxed Richardson method can be used, provided that a preliminary study for
the choice of the damping parameter is performed.

$N=d\cdot 2^{t}-1$ | $a(x)=1$ | $a(x)=x^{2}+1$ | $a(x)={\rm e}^{x}-2x$
---|---|---|---
$t$ | TGM | V-Cycle | TGM | V-Cycle | TGM | V-Cycle
4 | 6 | 6 | 7 | 7 | 6 | 7
5 | 6 | 6 | 7 | 7 | 6 | 7
6 | 6 | 6 | 7 | 7 | 6 | 7
7 | 6 | 6 | 7 | 7 | 6 | 7
8 | 6 | 6 | 7 | 7 | 6 | 7
9 | 6 | 6 | 7 | 7 | 6 | 7
10 | 6 | 6 | 7 | 7 | 6 | 7
Table 1:  Two-grid and V-cycle iterations in 1D for $a(x)=1,x^{2}+1,{\rm
e}^{x}-2x$, $tol=1\times 10^{-6}$.

##  6 Extension to multi-dimensional case

In the present subsection we give a possible extension of the convergence
results in the multidimensional setting. First, we need to introduce the
multi-index notation and define the objects of our analysis in more
dimensions.

Let ${\bf n}:=(n_{1},\ldots,n_{{m}})$ be a multi-index in $\mathbb{N}^{{m}}$
and set $N({r},\textbf{n}):={r}\prod_{i=1}^{{m}}n_{i}$. In particular, we need
to provide a generalized definition of the projector $P_{n,k}^{r}$ for the
${{m}}-$level block-circulant matrix
$A_{N}=\mathcal{A}_{\textbf{n}}(\mathbf{f})$ of dimension $N({r},\textbf{n})$
generated by a multilevel matrix-valued trigonometric polynomial $\mathbf{f}$.
A complete discussion on the multi-index notation can be found in [17].
Analogously to the scalar case, we want to construct the projectors from an
arbitrary multilevel block-circulant matrix
$\mathcal{A}_{\textbf{n}}(\mathbf{p})$, with $\mathbf{p}$ multivariate matrix-
valued trigonometric polynomial. For the construction of the projector we can
use a tensor product approach:

(50) $P_{\textbf{n},\textbf{k}}=\mathcal{A}_{\bf
n}(\mathbf{p})\left(K_{\textbf{n},\textbf{k}}^{Even}\otimes I_{r}\right),$

where $K_{\textbf{n},\textbf{k}}^{Even}$ is the
$N(1,\textbf{n})\times\frac{N(1,\textbf{n})}{2^{{{m}}}}$ matrix defined by
$K_{\textbf{n},\textbf{k}}^{Even}=K_{n_{1},k_{1}}^{Even}\otimes
K_{n_{2},k_{2}}^{Even}\otimes\dots\otimes K_{n_{{m}},k_{{m}}}^{Even}$ and
$\mathcal{A}_{\textbf{n}}(\mathbf{p})$ is a multilevel block-circulant matrix
generated by $\mathbf{p}$. The main goal is to combine the proof of Theorem
4.1 with the multilevel techniques in [30], in order to generalize conditions
(i)-(iii) to the multilevel case.

In the ${{m}}-$level setting, we are assuming that
$\boldsymbol{\theta}_{0}\in[0,2\pi)^{{m}}$ and
$\bar{\jmath}\in\\{1,\dots,r\\}$ such that

(51)
$\left\\{\begin{array}[]{ll}\lambda_{j}(\mathbf{f}(\boldsymbol{\theta}))=0&\mbox{for
}\boldsymbol{\theta}=\boldsymbol{\theta}_{0}\mbox{ and }j=\bar{\jmath},\\\
\lambda_{j}(\mathbf{f}(\boldsymbol{\theta}))>0&{\rm
otherwise}.\end{array}\right.$

The latter assumption means that the matrix $\mathbf{f}(\boldsymbol{\theta})$
has exactly one zero eigenvalue in $\boldsymbol{\theta}_{0}$ and it is
positive definite in $[0,2\pi)^{{m}}\backslash\\{\boldsymbol{\theta}_{0}\\}$.
Let us assume that, $q_{\bar{\jmath}}(\boldsymbol{\theta}_{0})$ is the
eigenvector of $\mathbf{f}(\boldsymbol{\theta}_{0})$ associated with
$\lambda_{\bar{\jmath}}(\mathbf{f}(\boldsymbol{\theta}_{0}))=0$. Moreover,
define
$\Omega(\boldsymbol{\theta})=\left\\{\boldsymbol{\theta}+\pi\boldsymbol{\eta},\,\boldsymbol{\eta}\in\\{0,1\\}^{{m}}\right\\}$.
Under these hypotheses, the multilevel extension of conditions (i)-(iii),
which are sufficient to ensure the optimal convergence of the TGM in the
multilevel case, is the following. Choose $\mathbf{p}(\cdot)$ such that

  * •

(52)
$\sum_{\xi\in\Omega(\boldsymbol{\theta})}\mathbf{p}(\xi)^{H}\mathbf{p}(\xi)>0,\quad\forall\,\boldsymbol{\theta}\in[0,2\pi)^{{m}},$

which implies that the trigonometric function

$\textbf{s}(\boldsymbol{\theta})=\mathbf{p}(\boldsymbol{\theta})\left(\sum_{\xi\in\Omega(\boldsymbol{\theta})}\mathbf{p}(\xi)^{H}\mathbf{p}(\xi)\right)^{-1}\mathbf{p}(\boldsymbol{\theta})^{H}$

is well-defined for all $\boldsymbol{\theta}\in[0,2\pi)^{{m}}$.

  * •

(53)
$\textbf{s}(\boldsymbol{\theta}_{0})q_{\bar{\jmath}}(\boldsymbol{\theta}_{0})=q_{\bar{\jmath}}(\boldsymbol{\theta}_{0}).$

  * •

(54)
$\lim_{\boldsymbol{\theta}\rightarrow\boldsymbol{\theta}_{0}}\lambda_{\bar{\jmath}}(\mathbf{f}(\boldsymbol{\theta}))^{-1}(1-\lambda_{\bar{\jmath}}(\textbf{s}(\boldsymbol{\theta})))=c,$

where $c\in\mathbb{R}$ is a constant.

In the following we want to construct a multilevel projector
$P_{\textbf{n},\textbf{k}}$ such that the conditions (52)-(54) are satisfied
and, then, the optimal convergence of the TGM, applied to the problem (30) in
the multidimensional setting, is ensured. In particular, starting from matrix-
valued trigonometric polynomials $\mathbf{p}_{r_{\ell}},$
$\ell=1,\dots,{{m}}$, we aim at defining a multivariate polynomial
$\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}$
associated to the multilevel projector $P_{{\textbf{n}},{\textbf{k}}}$ such
that the conditions (52)-(54) are satisfied.

In the following lemmas, we show that the aforementioned goal is achieved, if
we choose the multivariate matrix-valued trigonometric polynomial

(55)
$\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\theta_{1},\theta_{2},\dots,\theta_{{{m}}})=\bigotimes_{\ell=1}^{{{m}}}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}),$

where
$\mathbf{p}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{\ell}}}}(\theta_{\ell})\in\mathbb{C}^{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{\ell}}}\times{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{\ell}}}}$
are polynomials that satisfy conditions (i)-(iii).

######  Lemma 6.1.

Let
$\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\theta_{1},\theta_{2},\dots,\theta_{{{m}}})$
be defined as in (55). Then,

$\sum_{\xi\in\Omega(\boldsymbol{\theta})}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\xi)^{H}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\xi)=\bigotimes_{\ell=1}^{{{m}}}\left(\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right).$

######  Proof 6.2.

By definition,
$\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\boldsymbol{\theta})=\bigotimes_{\ell=1}^{{{m}}}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})$,
then

$\begin{split}\sum_{\xi\in\Omega(\boldsymbol{\theta})}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\xi)^{H}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\xi)&=\sum_{\xi\in\Omega(\boldsymbol{\theta})}\left(\bigotimes_{\ell=1}^{{{m}}}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\right)\left(\bigotimes_{\ell=1}^{{{m}}}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})\right)\\\
&=\sum_{\xi\in\Omega(\boldsymbol{\theta})}\left(\bigotimes_{\ell=1}^{{{m}}}\left(\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\mathbf{p}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{\ell}}}}(\xi_{\ell})\right)\right).\end{split}$

The proof is then concluded once we prove by induction on ${{m}}$ the
following equality

(56)
$\sum_{\xi\in\Omega(\boldsymbol{\theta})}\left(\bigotimes_{\ell=1}^{{{m}}}\left(\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\mathbf{p}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{\ell}}}}(\xi_{\ell})\right)\right)=\bigotimes_{\ell=1}^{{{m}}}\left(\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right).$

The equation above is clearly verified for ${{m}}=1$, indeed, by definition

$\displaystyle\sum_{\xi\in\Omega(\boldsymbol{\theta})}\left(\bigotimes_{\ell=1}^{1}\left(\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\mathbf{p}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{\ell}}}}(\xi_{\ell})\right)\right)=\sum_{\xi\in\\{\theta_{1},\theta_{1}+\pi\\}}\left(\mathbf{p}_{{r_{1}}}(\xi_{1})^{H}\mathbf{p}_{{r_{1}}}(\xi_{1})\right)=$
$\displaystyle\mathbf{p}_{r_{1}}(\theta_{1})^{H}\mathbf{p}_{{r_{1}}}(\theta_{1})+\mathbf{p}_{{r_{1}}}(\theta_{1}+\pi)^{H}\mathbf{p}_{{r_{1}}}(\theta_{1}+\pi)=$
$\displaystyle\bigotimes_{\ell=1}^{1}\left(\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right).$

Let us assume that equality (56) is true for ${{m}}-1$. We have that

$\begin{split}&\bigotimes_{\ell=1}^{{{m}}}\left(\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right)=\\\
&\left[\bigotimes_{\ell=1}^{{{m}}-1}\left(\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right)\right]\otimes\\\
&\left(\mathbf{p}_{{r_{{m}}}}(\theta_{{m}})^{H}\mathbf{p}_{{r_{{m}}}}(\theta_{{m}})+\mathbf{p}_{{r_{{m}}}}(\theta_{{m}}+\pi)^{H}\mathbf{p}_{{r_{{m}}}}(\theta_{{m}}+\pi)\right)\end{split}$

The left-hand side of the latter term is a function of ${{m}}-1$ variables
$(\theta_{1},\theta_{2},\dots,\theta_{{{m}}-1})$. Then, by the inductive
hypothesis and from the properties of the tensor product we have

$\displaystyle\left[\bigotimes_{\ell=1}^{{{m}}-1}\left(\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right)\right]\otimes$
$\displaystyle\left(\mathbf{p}_{{r_{{m}}}}(\theta_{{m}})^{H}\mathbf{p}_{{r_{{m}}}}(\theta_{{m}})+\mathbf{p}_{{r_{{m}}}}(\theta_{{m}}+\pi)^{H}\mathbf{p}_{{r_{{m}}}}(\theta_{{m}}+\pi)\right)=$
$\displaystyle\left(\sum_{\begin{subarray}{c}(\xi_{1},\xi_{2},\dots,\xi_{{{m}}-1})\\\
\in\\\
\Omega(\theta_{1},\theta_{2},\dots,\theta_{{{m}}-1})\end{subarray}}\bigotimes_{\ell=1}^{{{m}}-1}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})\right)\otimes$
$\displaystyle\left(\mathbf{p}_{{r_{{m}}}}(\theta_{{m}})^{H}\mathbf{p}_{{r_{{m}}}}(\theta_{{m}})+\mathbf{p}_{{r_{{m}}}}(\theta_{{m}}+\pi)^{H}\mathbf{p}_{{r_{{m}}}}(\theta_{{m}}+\pi)\right)=$
$\displaystyle\sum_{\begin{subarray}{c}(\xi_{1},\xi_{2},\dots,\xi_{{{m}}-1})\\\
\in\\\
\Omega(\theta_{1},\theta_{2},\dots,\theta_{{{m}}-1})\end{subarray}}\\!\\!\left[\\!\left(\bigotimes_{\ell=1}^{{{m}}-1}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})\\!\right)\\!\\!\otimes\\!\\!\left(\mathbf{p}_{{r_{{m}}}}(\theta_{{m}})^{H}\mathbf{p}_{{r_{{m}}}}(\theta_{{m}})\\!+\\!\mathbf{p}_{{r_{{m}}}}(\theta_{{m}}\\!+\\!\pi)^{H}\mathbf{p}_{{r_{{m}}}}(\theta_{{m}}\\!+\\!\pi)\\!\right)\\!\right]\\!\\!=$
$\displaystyle\sum_{\begin{subarray}{c}\xi\in\\{(\theta_{1}+l_{1}\pi,\dots,\theta_{{{m}}-1}+l_{{{m}}-1}\pi\\},\\\
\textbf{l}\in\\{0,1\\}^{{{m}}-1}\end{subarray}}\left[\left(\bigotimes_{\ell=1}^{{{m}}-1}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})\right)\otimes\mathbf{p}_{{r_{{m}}}}(\theta_{{m}})^{H}\mathbf{p}_{{r_{{m}}}}(\theta_{{m}})+\right.$
$\displaystyle+\left.\left(\bigotimes_{\ell=1}^{{{m}}-1}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})\right)\otimes\mathbf{p}_{{r_{{m}}}}(\theta_{{m}}+\pi)^{H}\mathbf{p}_{{r_{{m}}}}(\theta_{{m}}+\pi)\right]=$
$\displaystyle\sum_{\begin{subarray}{c}\xi\in\\{(\theta_{1}+l_{1}\pi,\dots,\theta_{{{m}}-1}+l_{{{m}}-1}\pi,\theta_{{{m}}})\\},\\\
\textbf{l}\in\\{0,1\\}^{{{m}}-1}\end{subarray}}\bigotimes_{\ell=1}^{{{m}}}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})+$
$\displaystyle\sum_{\begin{subarray}{c}\xi\in\\{(\theta_{1}+l_{1}\pi,\dots,\theta_{{{m}}-1}+l_{{{m}}-1}\pi,\theta_{{{m}}}+\pi)\\},\\\
\textbf{l}\in\\{0,1\\}^{{{m}}-1}\end{subarray}}\bigotimes_{\ell=1}^{{{m}}}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})=$
$\displaystyle\sum_{\xi\in\Omega(\boldsymbol{\theta})}\bigotimes_{\ell=1}^{{{m}}}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\xi_{\ell}).$

Then, relation (56) is verified for ${{m}}$, and this concludes the proof.

######  Lemma 6.3.

Let
$\mathbf{p}^{({{m}})}_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}(\theta_{1},\theta_{2},\dots,\theta_{{{m}}})$
defined as in (55) where $\mathbf{p}_{{r_{\ell}}}$, for every
$\ell=1,\dots,{{m}}$, is a polynomial which verifies the positivity condition
(i). Then, $\mathbf{p}^{({{m}})}_{{r}}$ is such that the positivity condition
in the multilevel setting (52) is satisfied.

######  Proof 6.4.

The thesis is consequence of Lemma 6.1 and the matrix tensor product
properties. Indeed, the eigenvalues of a tensor product of matrices are the
product of the eigenvalues of the matrices. Then, condition (52) is trivially
implied from the fact that

$\sum_{\xi\in\Omega(\boldsymbol{\theta})}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\xi)^{H}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\xi)=\bigotimes_{\ell=1}^{{{m}}}\left(\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right),$

and from the positivity condition holding in the unilevel case.

######  Lemma 6.5.

Let
$\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\theta_{1},\theta_{2},\dots,\theta_{{{m}}})$
be defined as in (55) and it verifies (52). Then, the trigonometric function

$\textbf{s}(\boldsymbol{\theta})=\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\boldsymbol{\theta})\left(\sum_{\xi\in\Omega(\boldsymbol{\theta})}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\xi)^{H}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\xi)\right)^{-1}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\boldsymbol{\theta})^{H}$

is well-defined for all $\boldsymbol{\theta}\in[0,2\pi)^{{m}}$. Moreover, it
holds

(57)
$\textbf{s}(\boldsymbol{\theta})=\bigotimes_{\ell=1}^{{{m}}}\textbf{s}_{{r_{\ell}}}(\theta_{\ell}),$

where
$\textbf{s}_{{r_{\ell}}}(\theta_{\ell})=\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})\left(\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right)^{-1}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}$,
for $\ell=1,\dots,{{m}}$.

######  Proof 6.6.

From Lemma 6.3, we have that $\textbf{s}(\boldsymbol{\theta})$ is well-defined
for all $\boldsymbol{\theta}\in[0,2\pi)^{{m}}$. From Lemma 6.1 and the
properties of the tensor product, we have

(58)
$\begin{split}&\textbf{s}(\boldsymbol{\theta})=\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\boldsymbol{\theta})\left(\sum_{\xi\in\Omega(\boldsymbol{\theta})}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\xi)^{H}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\xi)\right)^{-1}\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\boldsymbol{\theta})^{H}=\\\
&\bigotimes_{\ell=1}^{{{m}}}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})\left(\bigotimes_{\ell=1}^{{{m}}}\left[\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right]^{-1}\right)\bigotimes_{\ell=1}^{{{m}}}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}=\\\
&\bigotimes_{\ell=1}^{{{m}}}\left(\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})\left[\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right]^{-1}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\right)=\bigotimes_{\ell=1}^{{{m}}}\textbf{s}_{{r_{\ell}}}(\theta_{\ell}).\end{split}$

.

######  Lemma 6.7.

Let
$\mathbf{p}^{({{m}})}_{{}_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\theta_{1},\theta_{2},\dots,\theta_{{{m}}})$
be defined as in (55), such that, for all $\ell=1,\dots,{{m}}$,
$\mathbf{p}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{\ell}}}}(\theta_{\ell})\in\mathbb{C}^{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{\ell}}}\times{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r_{\ell}}}}$
is a polynomial that satisfies conditions (i)-(iii). Let
${q}_{\mathbf{r}}=\bigotimes_{\ell=1,\dots,{{m}}}{\rm q}_{r_{\ell}}$, where
${\rm q}_{r_{\ell}}$ is the column vector of length $r_{\ell}$ such that
$\textbf{s}_{{r_{\ell}}}({\theta_{0}^{(\ell)}}){\rm q}_{r_{\ell}}={\rm
q}_{r_{\ell}}$, $\ell=1,\dots,{{m}}$. Then,

$\textbf{s}(\boldsymbol{\theta_{0}}){q}_{\mathbf{r}}={q}_{\mathbf{r}},\qquad\mbox{where
}\boldsymbol{\theta}_{0}=\left(\theta_{0}^{(1)},\dots,\theta_{0}^{({{m}})}\right).$

######  Proof 6.8.

From Lemma 6.5, we have that
$\textbf{s}(\boldsymbol{\theta_{0}})=\bigotimes_{\ell=1}^{{{m}}}\textbf{s}_{{r_{\ell}}}(\theta_{0}),$
then, by definition and from the properties of the tensor product, it holds

(59)
$\textbf{s}(\boldsymbol{\theta_{0}}){q}_{\mathbf{r}}=\left(\bigotimes_{\ell=1}^{{{m}}}\textbf{s}_{{r_{\ell}}}(\theta_{0})\right)\left(\bigotimes_{\ell=1}^{{{m}}}{\rm
q}_{r_{\ell}}\right)=\bigotimes_{\ell=1}^{{{m}}}\left(\textbf{s}_{{r_{\ell}}}(\theta_{0}){\rm
q}_{r_{\ell}}\right)=\bigotimes_{\ell=1}^{{{m}}}{\rm
q}_{r_{\ell}}={q}_{\mathbf{r}}.$

######  Lemma 6.9.

Let
$\mathbf{p}^{({{m}})}_{{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathbf{r}}}}(\theta_{1},\theta_{2},\dots,\theta_{{{m}}})$
be defined as in (55) such that verifies (52). Consider
$\textbf{s}(\boldsymbol{\theta})=\bigotimes_{\ell=1}^{{{m}}}\textbf{s}_{{r_{\ell}}}(\theta_{\ell}),$
where

$\textbf{s}_{{r_{\ell}}}(\theta_{\ell})=\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})\left(\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})+\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)^{H}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell}+\pi)\right)^{-1}\mathbf{p}_{{r_{\ell}}}(\theta_{\ell})^{H},$

for $\ell=1,\dots,{{m}}$, and they verify condition $(iii)$. Then,
$\textbf{s}(\boldsymbol{\theta})$ satisfies condition (54).

######  Proof 6.10.

Without loss of generality, suppose that the order of the zero of
$\lambda_{\bar{\jmath}}\left(\mathbf{f}({\theta_{\ell}})\right)$ in
$\theta_{0}$ is $\varsigma\geq 2$ for $\ell=1,\dots,{{m}}$, then the functions
$1-\lambda_{\bar{\jmath}}\left(\textbf{s}_{{r_{\ell}}}(\theta_{\ell})\right)$
have a zero in $\theta_{0}$ of order at least $\varsigma\in\mathbb{N}$ for all
$\ell=1,\dots,{{m}}$ by condition (iii). Hence, the $(\varsigma-1)$-th
derivative of
$1-\lambda_{\bar{\jmath}}\left(\textbf{s}_{{r_{\ell}}}(\theta_{\ell})\right)$
in $\theta_{0}$ is equal to zero. Then we have, for $\ell=1,\dots,{{m}}$,

$\left.\lambda_{\bar{\jmath}}\left(\textbf{s}_{{r_{\ell}}}(\theta_{\ell})\right)^{(\varsigma-1)}\right|_{\theta_{0}}=0.$

The thesis follows by direct computation of the partial derivatives of
$1-\lambda_{\bar{\jmath}}(\textbf{s}(\boldsymbol{\theta}))$ in
$\boldsymbol{\theta}_{0}$, exploiting the fact that

$\textbf{s}(\boldsymbol{\theta})=\bigotimes_{\ell=1}^{{{m}}}\textbf{s}_{{r_{\ell}}}(\theta_{\ell})\qquad\mbox{and}\qquad\lambda_{\bar{\jmath}}\left(\textbf{s}(\boldsymbol{\theta})\right)=\prod_{\ell=1}^{{{m}}}\lambda_{\bar{\jmath}}\left(\textbf{s}_{{r_{\ell}}}(\theta_{\ell})\right).$

.

##  7 Conclusions and Future Developments

We derived the conditions which ensure the optimal convergence rate of both
the TGM and the V-cycle method when applied to (multilevel) block-circulant
and (multilevel) block-Toeplitz matrices. In particular, we focused on the
case where the generating function $\mathbf{f}$ is a matrix-valued
trigonometric polynomial and we provide several simplifications for the
validation of the theoretical conditions in practical cases. We also
generalized the results for multilevel block-Toeplitz matrices.

As a final comment, we emphasize that the one of the main aims of the paper
was to give a theoretical ground to the optimal multigrid convergence for
block structured matrices, where optimal means with a convergence rate
independent of the matrix size. Moreover, it provided analytical proofs of the
effectiveness of standard projectors, largely used in classical applications
[20]. The numerical potency of the projectors treated in subsections 5.2-5.3
has been exploited in many different settings (multilevel, variable
coefficients case) with optimal results. In addition to Table 1, see Tables
1–6 in [14] and Table V.7 in [13].

## Acknowledgments

The work of Marco Donatelli, Paola Ferrari, Isabella Furci is partially
supported by Gruppo Nazionale per il Calcolo Scientifico (GNCS-INdAM).

## References

  * [1] A. Aricò and M. Donatelli, A v-cycle multigrid for multilevel matrix algebras: proof of optimality, Numer. Math., 105 (2007), pp. 511–547.
  * [2] A. Aricò, M. Donatelli, and S. Serra-Capizzano, V-cycle optimal convergence for certain (multilevel) structured linear systems, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 186–214.
  * [3] R. Bhatia, Matrix analysis, vol. 169 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1997.
  * [4] D. Braess, Finite elements, Cambridge University Press, Cambridge, third ed., 2007.  Theory, fast solvers, and applications in elasticity theory, Translated from the German by Larry L. Schumaker.
  * [5] D. Braess, Finite elements: Theory, fast solvers, and applications in solid mechanics, Cambridge University Press, 2007.
  * [6] A. Brandt, Rigorous quantitative analysis of multigrid, i. constant coefficients two-level cycle with l_2-norm, SIAM Journal on Numerical Analysis, 31 (1994), pp. 1695–1730.
  * [7] W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, Second Edition, SIAM, second ed., 2000.
  * [8] R. H. Chan, Q.-S. Chang, and H.-W. Sun, Multigrid method for ill-conditioned symmetric Toeplitz systems, SIAM J. Sci. Comput., 19 (1998), pp. 516–529.
  * [9] V. Del Prete, F. Di Benedetto, M. Donatelli, and S. Serra-Capizzano, Symbol approach in a signal-restoration problem involving block toeplitz matrices, Journal of Computational and Applied Mathematics, 272 (2014), pp. 399–416.
  * [10] M. Donatelli, A multigrid for image deblurring with tikhonov regularization, Numerical Linear Algebra with Applications, 12 (2005), pp. 715–729.
  * [11] M. Donatelli, An algebraic generalization of local fourier analysis for grid transfer operators in multigrid based on toeplitz matrices, Numerical Linear Algebra with Applications, 17 (2010), pp. 179–197.
  * [12] M. Donatelli, P. Ferrari, I. Furci, D. Sesana, and S. Serra-Capizzano, Multigrid methods for block-circulant and block-Toeplitz large linear systems: Algorithmic proposals and two-grid optimality analysis, Numer. Linear Algebra Appl., e2356 (2020).
  * [13] P. Ferrari, Toeplitz and block-toeplitz structures with variants: From the spectral analysis to preconditioning and multigrid methods using a symbol approach.  Ph.D. Thesis, Insubria University, 2020.