<p>We consider block-structured matrices <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\varvec{A}_{\varvec{n}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>, where the blocks are of (block) unilevel Toeplitz type with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varvec{s\times t}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">s</mi> <mo mathvariant="bold">×</mo> <mi mathvariant="bold-italic">t</mi> </mrow> </math></EquationSource> </InlineEquation> matrix-valued generating functions. Under mild assumptions on the size of the (rectangular) blocks, the asymptotic distribution of the singular values of the associated matrix-sequences is identified and, when the related singular value symbol is Hermitian, it coincides with the spectral symbol. Building on the theoretical derivations, we approximate the matrices with simplified block structures that show two important features: a) the related simplified matrix-sequence has the same distributions as <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\varvec{\{}\varvec{A}_{\varvec{n}}\varvec{\}}_{\varvec{n}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo mathvariant="bold" stretchy="false">{</mo> </mrow> <msub> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </msub> <msub> <mrow> <mo mathvariant="bold" stretchy="false">}</mo> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>; b) a generic linear system involving the simplified structures can be solved in <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\varvec{O(n\log n)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">O</mi> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold">log</mo> <mi mathvariant="bold-italic">n</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> arithmetic operations. The two key properties a) and b) suggest a natural way for preconditioning a linear system with coefficient matrix <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\varvec{A}_{\varvec{n}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-italic">A</mi> </mrow> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>. Under mild assumptions, the singular value analysis and the spectral analysis of the preconditioned matrix-sequences is provided, together with a wide set of numerical experiments.</p>

Blocking structures, approximation, and preconditioning

期刊论文
发表日期：

2025年7月8日

查看全文

Nikos Barakitis,
Marco Donatelli,
Samuele Ferri,
Valerio Loi,
Stefano Serra-Capizzano,
Rosita Luisa Sormani

摘要

We consider block-structured matrices $\varvec{A}_{\varvec{n}}$ $A_{n}$ , where the blocks are of (block) unilevel Toeplitz type with $\varvec{s\times t}$ $s \times t$ matrix-valued generating functions. Under mild assumptions on the size of the (rectangular) blocks, the asymptotic distribution of the singular values of the associated matrix-sequences is identified and, when the related singular value symbol is Hermitian, it coincides with the spectral symbol. Building on the theoretical derivations, we approximate the matrices with simplified block structures that show two important features: a) the related simplified matrix-sequence has the same distributions as $\varvec{\{}\varvec{A}_{\varvec{n}}\varvec{\}}_{\varvec{n}}$ ${A_{n}}_{n}$ ; b) a generic linear system involving the simplified structures can be solved in $\varvec{O(n\log n)}$ $O (n log n)$ arithmetic operations. The two key properties a) and b) suggest a natural way for preconditioning a linear system with coefficient matrix $\varvec{A}_{\varvec{n}}$ $A_{n}$ . Under mild assumptions, the singular value analysis and the spectral analysis of the preconditioned matrix-sequences is provided, together with a wide set of numerical experiments.