Bini / Di Benedetto / Tyrtyshnikov Structured Matrices in Numerical Linear Algebra

Analysis, Algorithms and Applications
1. Auflage 2019
ISBN: 978-3-030-04088-8
Verlag: Springer International Publishing
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 30, 327 Seiten

Reihe: Springer INdAM Series

This book gathers selected contributions presented at the INdAM Meeting Structured Matrices in Numerical Linear Algebra: Analysis, Algorithms and Applications, held in Cortona, Italy on September 4-8, 2017. Highlights cutting-edge research on Structured Matrix Analysis, it covers theoretical issues, computational aspects, and applications alike. The contributions, written by authors from the foremost international groups in the community, trace the main research lines and treat the main problems of current interest in this field. The book offers a valuable resource for all scholars who are interested in this topic, including researchers, PhD students and post-docs.


Dario A. Bini, a Full Professor of Numerical Analysis since 1986, has held a permanent position at the University of Pisa since 1989. His research mainly focuses on numerical linear algebra problems, on structured matrix analysis and on the design and analysis of algorithms for polynomial and matrix computations. The author of three research books and more than 120 papers, he also serves on the editorial boards of three international journals.Fabio Di Benedetto has been an Associate Professor of Numerical Analysis at the Department of Mathematics of the University of Genova, where he teaches courses on Numerical Analysis for undergraduate and graduate students, since 2000. His main research interests concern the solution of large-scale numerical linear algebra problems, with special attention to structured matrices analysis with applications to image processing. He is the author of more than 30 papers.Eugene Tyrtyshnikov, Professor and Chairman at the Lomonosov Moscow State University, is a Full Member of the Russian Academy of Sciences and Director of the Institute of Numerical Mathematics of the Russian Academy of Sciences, Moscow. He completed his Ph.D. in Numerical Mathematics at Moscow State University, and his postdoctoral studies at the Siberian Branch of the Russian Academy of Sciences, Novosibirsk. His research interests concern numerical analysis, linear and multilinear algebra, approximation theory and related applications. He is the associate editor of many international journals and the author of more than 100 papers and 8 books. Marc Van Barel received his Ph.D. in Computer Engineering (Numerical Analysis and Applied Mathematics) from the KU Leuven, where he is currently a Full Professor at the Department of Computer Science. His work mainly focuses on numerical (multi-)linear algebra, approximation theory, orthogonal functions and their applications in systems theory, signal processing, machine learning, etc. He is the author or co-author of more than 140 papers and 4 books. Currently, he serves on the editorial boards of three international journals.

Autoren/Hrsg.

Bini, Dario Andrea

Di Benedetto, Fabio

Tyrtyshnikov, Eugene

Barel, Marc Van

Inhaltsverzeichnis

1;Preface;6
2;Contents;8
3;About the Editors;10
4;Spectral Measures;11
4.1;1 Introduction;11
4.2;2 Prerequisites;13
4.2.1;2.1 Complete Pseudometrics;13
4.2.2;2.2 Optimal Matching Distance;15
4.2.3;2.3 GLT Matrix Sequences;19
4.3;3 Spectral Measures;20
4.3.1;3.1 Radon Measures;20
4.3.2;3.2 Vague Convergence;24
4.4;4 Main Results;27
4.4.1;4.1 Connection Between Measures;27
4.4.2;4.2 Proofs of Theorems;31
4.5;5 Future Works;33
4.6;References;33
5;Block Locally Toeplitz Sequences: Construction and Properties;35
5.1;1 Introduction;35
5.2;2 Mathematical Background;38
5.2.1;2.1 Notation and Terminology;38
5.2.2;2.2 Preliminaries on Matrix Analysis;39
5.2.2.1;2.2.1 Matrix Norms;39
5.2.2.2;2.2.2 Direct Sums and Hadamard Products;40
5.2.3;2.3 Preliminaries on Measure and Integration Theory;40
5.2.3.1;2.3.1 Measurability;40
5.2.3.2;2.3.2 Lp-Norms of Matrix-Valued Functions;41
5.2.3.3;2.3.3 Convergence in Measure;41
5.2.4;2.4 Singular Value and Eigenvalue Distribution of a Matrix-Sequence;43
5.2.5;2.5 Zero-Distributed Sequences;44
5.2.6;2.6 Sparsely Unbounded Matrix-Sequences;44
5.2.7;2.7 Block Toeplitz Matrices;46
5.3;3 Approximating Classes of Sequences;48
5.3.1;3.1 The a.c.s. Notion;48
5.3.2;3.2 The a.c.s. Tools for Computing Singular Value and Eigenvalue Distributions;49
5.3.3;3.3 The a.c.s. Algebra;51
5.3.4;3.4 A Criterion to Identify a.c.s.;52
5.4;4 Block Locally Toeplitz Sequences;52
5.4.1;4.1 The Block LT Operator;52
5.4.2;4.2 Definition of Block LT Sequences;58
5.4.3;4.3 Zero-Distributed Sequences, Sequences of Block Diagonal Sampling Matrices, and Sequences of Block Toeplitz Matrices;58
5.4.3.1;4.3.1 Zero-Distributed Sequences;58
5.4.3.2;4.3.2 Sequences of Block Diagonal Sampling Matrices;59
5.4.3.3;4.3.3 Sequences of Block Toeplitz Matrices;63
5.4.4;4.4 Singular Value and Spectral Distribution of a Sum of Products of Block LT Sequences;65
5.5;5 Concluding Remarks;66
5.6;References;67
6;Block Generalized Locally Toeplitz Sequences: Topological Construction, Spectral Distribution Results, and Star-Algebra Structure;69
6.1;1 Introduction;70
6.2;2 Mathematical Background;71
6.2.1;2.1 Notation and Terminology;71
6.2.2;2.2 Preliminaries on Measure and Integration Theory;72
6.2.2.1;2.2.1 Measurability;72
6.2.2.2;2.2.2 Convergence in Measure;72
6.2.2.3;2.2.3 Technical Lemma;73
6.2.3;2.3 Singular Value and Eigenvalue Distribution of a Matrix-Sequence;74
6.2.4;2.4 Zero-Distributed Sequences;75
6.2.5;2.5 Sparsely Unbounded and Sparsely Vanishing Matrix-Sequences;75
6.2.6;2.6 Block Toeplitz Matrices;77
6.3;3 Approximating Classes of Sequences;77
6.4;4 Block Locally Toeplitz Sequences;79
6.5;5 Block Generalized Locally Toeplitz Sequences;80
6.5.1;5.1 Equivalent Definitions of Block GLT Sequences;80
6.5.2;5.2 Singular Value and Spectral Distribution of Block GLT Sequences;82
6.5.3;5.3 The GLT Algebra;84
6.6;6 Summary of the Theory;85
6.7;7 Final Remarks;86
6.8;References;87
7;On Matrix Subspaces with Trivial Quadratic Kernels;90
7.1;1 Introduction and Preliminaries;90
7.2;2 Maximal Rank Consequences;94
7.3;3 Particular Cases Without Symmetry;97
7.4;References;99
8;Error Analysis of TT-Format Tensor Algorithms;100
8.1;1 Introduction;100
8.2;2 Notations and Preliminaries;102
8.2.1;2.1 The Tensor Train Format for Multidimensional Arrays;103
8.3;3 Full-to-TT Compression;103
8.3.1;3.1 Backward Stability Analysis;107
8.4;4 Computing Multilinear Forms;110
8.5;Appendix;113
8.6;References;115
9;The Derivative of the Matrix Geometric Mean with an Application to the Nonnegative Decomposition of Tensor Grids;116
9.1;1 Introduction;116
9.2;2 The Geometry of P? and the Matrix Geometric Mean;118
9.3;3 Computing the Weighted Matrix Geometric Mean and Its Derivative;119
9.3.1;3.1 Computing the Weighted Matrix Geometric Mean;120
9.3.2;3.2 The Derivative of the Matrix Geometric Mean;121
9.4;4 Factorization of Tensor Grids;125
9.4.1;4.1 A Simple Algorithm for the Matrix Geometric Mean Decomposition;127
9.4.1.1;4.1.1 The Gradients of R(U,V);128
9.4.1.2;4.1.2 The Gradients of L(U,V);130
9.5;5 Numerical Experiments;132
9.5.1;5.1 Basic Dataset;133
9.5.2;5.2 Geometrically Varying Dataset;133
9.5.3;5.3 Speed Test;135
9.6;6 Conclusions;136
9.7;References;136
10;Factoring Block Fiedler Companion Matrices;138
10.1;1 Introduction;139
10.2;2 Fiedler Graphs and (Block) Fiedler Companion Matrices;141
10.3;3 Factoring Elementary Block Fiedler Factors;145
10.3.1;3.1 Block Factors Fi, for i>0;145
10.3.2;3.2 The Block Fiedler Factor F0;149
10.4;4 Factoring Block Companion Matrices;151
10.5;5 Unitary-Plus-Low-Rank Structure;157
10.6;6 A Thin-Banded Linearization;159
10.7;7 Conclusions;162
10.8;References;162
11;A Class of Quasi-Sparse Companion Pencils;165
11.1;1 Introduction;165
11.2;2 Preliminaries;167
11.2.1;2.1 New Classes of Block-Partitioned Pencils;168
11.3;3 Companion Pencils in Qn,k;171
11.4;4 Number of Different Sparse Companion Pencils in Rn,k;175
11.5;5 Conclusions;186
11.6;References;186
12;On Computing Eigenvectors of Symmetric Tridiagonal Matrices;188
12.1;1 Introduction;189
12.2;2 Notations and Definitions;189
12.3;3 Implicit QR Method;190
12.4;4 Computation of the Eigenvector;196
12.5;5 Deflation;198
12.6;6 Numerical Examples;199
12.7;7 Conclusions;201
12.8;References;201
13;A Krylov Subspace Method for the Approximation of Bivariate Matrix Functions;203
13.1;1 Introduction;203
13.2;2 Preliminaries;205
13.3;3 Algorithm;207
13.4;4 Exactness Properties and Convergence Analysis;209
13.5;5 Application to Fréchet Derivatives;213
13.6;6 Outlook;216
13.7;Appendix: Polynomial Approximation of the ? Function;216
13.8;References;219
14;Uzawa-Type and Augmented Lagrangian Methods for Double Saddle Point Systems;221
14.1;1 Introduction;222
14.2;2 Uzawa-Like Iterative Schemes;223
14.2.1;2.1 Double Saddle Point Problems with Zero (3,3)-Block;224
14.2.2;2.2 Double Saddle Point Problems with SPD (3,3)-Block;226
14.2.3;2.3 Augmenting the (1,1)-Block of Double Saddle Point Problems;229
14.3;3 A Generalization of the Block SOR Method;232
14.4;4 Numerical Experiments;234
14.5;5 Conclusions;241
14.6;References;241
15;Generalized Block Tuned Preconditioners for SPD Eigensolvers;243
15.1;1 Introduction;243
15.2;2 The Generalized Tuned Preconditioner;245
15.3;3 Algorithmic Issues;250
15.3.1;3.1 Repeated Application of the GBT Preconditioner;251
15.4;4 Numerical Results;252
15.4.1;4.1 Matrices with Clustered Small Eigenvalues;252
15.4.2;4.2 Summary of Results on the Remaining Matrices;257
15.5;5 Conclusions;257
15.6;References;258
16;Stability of Gyroscopic Systems with Respect to Perturbations;259
16.1;1 Introduction;259
16.2;2 Distance to Instability;261
16.2.1;2.1 Methodology;262
16.2.2;2.2 Algorithm;263
16.3;3 The Gradient System of ODEs;263
16.3.1;3.1 The System of ODEs;266
16.4;4 The Computation of the Distance to Instability;267
16.4.1;4.1 Variational Formula for the -Pseudoeigenvalues with Respect to;268
16.5;5 The Complete Algorithm;269
16.6;6 Numerical Experiments;270
16.6.1;6.1 Example 1;270
16.6.2;6.2 Example 2;271
16.6.3;6.3 Example 3;272
16.7;References;272
17;Energetic BEM for the Numerical Solution of 2D Hard Scattering Problems of Damped Waves by Open Arcs;273
17.1;1 Introduction;273
17.2;2 Model Problem and Its Weak Boundary Integral Formulation;275
17.3;3 Energetic BEM Discretization;278
17.4;4 An FFT-Based Algorithm for MoT Computation;279
17.5;5 Numerical Results;284
17.6;6 Conclusions;288
17.7;References;288
18;Efficient Preconditioner Updates for Semilinear Space–Time Fractional Reaction–Diffusion Equations;290
18.1;1 Introduction and Rationale;291
18.2;2 Fractional Linear Multistep Formulas or FLMMs;292
18.3;3 Preconditioning the Linear Systems of the Newton Iterations;295
18.4;4 Numerical Experiments;299
18.4.1;4.1 A Time-Fractional Biological Population Model;299
18.5;References;306
19;A Nuclear-Norm Model for Multi-Frame Super-Resolution Reconstruction from Video Clips;308
19.1;1 Introduction;308
19.2;2 Low-Resolution Model with Shifts;311
19.3;3 Nuclear-Norm Model;312
19.3.1;3.1 Decomposition of the Warping Matrices;313
19.3.2;3.2 Algorithm for Solving the Nuclear-Norm Model;315
19.3.3;3.3 Image Registration and Parameter Selection;316
19.4;4 Numerical Experiments;318
19.4.1;4.1 Synthetic Videos;319
19.4.2;4.2 Real Videos;322
19.5;5 Conclusion;326
19.6;References;326