Structured Matrices in Numerical Linear Algebra (eBook)

Preface 6
Contents 8
About the Editors 10
Spectral Measures 11
1 Introduction 11
2 Prerequisites 13
2.1 Complete Pseudometrics 13
2.2 Optimal Matching Distance 15
2.3 GLT Matrix Sequences 19
3 Spectral Measures 20
3.1 Radon Measures 20
3.2 Vague Convergence 24
4 Main Results 27
4.1 Connection Between Measures 27
4.2 Proofs of Theorems 31
5 Future Works 33
References 33
Block Locally Toeplitz Sequences: Construction and Properties 35
1 Introduction 35
2 Mathematical Background 38
2.1 Notation and Terminology 38
2.2 Preliminaries on Matrix Analysis 39
2.2.1 Matrix Norms 39
2.2.2 Direct Sums and Hadamard Products 40
2.3 Preliminaries on Measure and Integration Theory 40
2.3.1 Measurability 40
2.3.2 Lp-Norms of Matrix-Valued Functions 41
2.3.3 Convergence in Measure 41
2.4 Singular Value and Eigenvalue Distribution of a Matrix-Sequence 43
2.5 Zero-Distributed Sequences 44
2.6 Sparsely Unbounded Matrix-Sequences 44
2.7 Block Toeplitz Matrices 46
3 Approximating Classes of Sequences 48
3.1 The a.c.s. Notion 48
3.2 The a.c.s. Tools for Computing Singular Value and Eigenvalue Distributions 49
3.3 The a.c.s. Algebra 51
3.4 A Criterion to Identify a.c.s. 52
4 Block Locally Toeplitz Sequences 52
4.1 The Block LT Operator 52
4.2 Definition of Block LT Sequences 58
4.3 Zero-Distributed Sequences, Sequences of Block Diagonal Sampling Matrices, and Sequences of Block Toeplitz Matrices 58
4.3.1 Zero-Distributed Sequences 58
4.3.2 Sequences of Block Diagonal Sampling Matrices 59
4.3.3 Sequences of Block Toeplitz Matrices 63
4.4 Singular Value and Spectral Distribution of a Sum of Products of Block LT Sequences 65
5 Concluding Remarks 66
References 67
Block Generalized Locally Toeplitz Sequences: Topological Construction, Spectral Distribution Results, and Star-Algebra Structure 69
1 Introduction 70
2 Mathematical Background 71
2.1 Notation and Terminology 71
2.2 Preliminaries on Measure and Integration Theory 72
2.2.1 Measurability 72
2.2.2 Convergence in Measure 72
2.2.3 Technical Lemma 73
2.3 Singular Value and Eigenvalue Distribution of a Matrix-Sequence 74
2.4 Zero-Distributed Sequences 75
2.5 Sparsely Unbounded and Sparsely Vanishing Matrix-Sequences 75
2.6 Block Toeplitz Matrices 77
3 Approximating Classes of Sequences 77
4 Block Locally Toeplitz Sequences 79
5 Block Generalized Locally Toeplitz Sequences 80
5.1 Equivalent Definitions of Block GLT Sequences 80
5.2 Singular Value and Spectral Distribution of Block GLT Sequences 82
5.3 The GLT Algebra 84
6 Summary of the Theory 85
7 Final Remarks 86
References 87
On Matrix Subspaces with Trivial Quadratic Kernels 90
1 Introduction and Preliminaries 90
2 Maximal Rank Consequences 94
3 Particular Cases Without Symmetry 97
References 99
Error Analysis of TT-Format Tensor Algorithms 100
1 Introduction 100
2 Notations and Preliminaries 102
2.1 The Tensor Train Format for Multidimensional Arrays 103
3 Full-to-TT Compression 103
3.1 Backward Stability Analysis 107
4 Computing Multilinear Forms 110
Appendix 113
References 115
The Derivative of the Matrix Geometric Mean with an Application to the Nonnegative Decomposition of Tensor Grids 116
1 Introduction 116
2 The Geometry of P? and the Matrix Geometric Mean 118
3 Computing the Weighted Matrix Geometric Mean and Its Derivative 119
3.1 Computing the Weighted Matrix Geometric Mean 120
3.2 The Derivative of the Matrix Geometric Mean 121
4 Factorization of Tensor Grids 125
4.1 A Simple Algorithm for the Matrix Geometric Mean Decomposition 127
4.1.1 The Gradients of R(U,V) 128
4.1.2 The Gradients of L(U,V) 130
5 Numerical Experiments 132
5.1 Basic Dataset 133
5.2 Geometrically Varying Dataset 133
5.3 Speed Test 135
6 Conclusions 136
References 136
Factoring Block Fiedler Companion Matrices 138
1 Introduction 139
2 Fiedler Graphs and (Block) Fiedler Companion Matrices 141
3 Factoring Elementary Block Fiedler Factors 145
3.1 Block Factors Fi, for i> 0
3.2 The Block Fiedler Factor F0 149
4 Factoring Block Companion Matrices 151
5 Unitary-Plus-Low-Rank Structure 157
6 A Thin-Banded Linearization 159
7 Conclusions 162
References 162
A Class of Quasi-Sparse Companion Pencils 165
1 Introduction 165
2 Preliminaries 167
2.1 New Classes of Block-Partitioned Pencils 168
3 Companion Pencils in Qn,k 171
4 Number of Different Sparse Companion Pencils in Rn,k 175
5 Conclusions 186
References 186
On Computing Eigenvectors of Symmetric Tridiagonal Matrices 188
1 Introduction 189
2 Notations and Definitions 189
3 Implicit QR Method 190
4 Computation of the Eigenvector 196
5 Deflation 198
6 Numerical Examples 199
7 Conclusions 201
References 201
A Krylov Subspace Method for the Approximation of Bivariate Matrix Functions 203
1 Introduction 203
2 Preliminaries 205
3 Algorithm 207
4 Exactness Properties and Convergence Analysis 209
5 Application to Fréchet Derivatives 213
6 Outlook 216
Appendix: Polynomial Approximation of the ? Function 216
References 219
Uzawa-Type and Augmented Lagrangian Methods for Double Saddle Point Systems 221
1 Introduction 222
2 Uzawa-Like Iterative Schemes 223
2.1 Double Saddle Point Problems with Zero (3,3)-Block 224
2.2 Double Saddle Point Problems with SPD (3,3)-Block 226
2.3 Augmenting the (1,1)-Block of Double Saddle Point Problems 229
3 A Generalization of the Block SOR Method 232
4 Numerical Experiments 234
5 Conclusions 241
References 241
Generalized Block Tuned Preconditioners for SPD Eigensolvers 243
1 Introduction 243
2 The Generalized Tuned Preconditioner 245
3 Algorithmic Issues 250
3.1 Repeated Application of the GBT Preconditioner 251
4 Numerical Results 252
4.1 Matrices with Clustered Small Eigenvalues 252
4.2 Summary of Results on the Remaining Matrices 257
5 Conclusions 257
References 258
Stability of Gyroscopic Systems with Respect to Perturbations 259
1 Introduction 259
2 Distance to Instability 261
2.1 Methodology 262
2.2 Algorithm 263
3 The Gradient System of ODEs 263
3.1 The System of ODEs 266
4 The Computation of the Distance to Instability 267
4.1 Variational Formula for the -Pseudoeigenvalues with Respect to 268
5 The Complete Algorithm 269
6 Numerical Experiments 270
6.1 Example 1 270
6.2 Example 2 271
6.3 Example 3 272
References 272
Energetic BEM for the Numerical Solution of 2D Hard Scattering Problems of Damped Waves by Open Arcs 273
1 Introduction 273
2 Model Problem and Its Weak Boundary Integral Formulation 275
3 Energetic BEM Discretization 278
4 An FFT-Based Algorithm for MoT Computation 279
5 Numerical Results 284
6 Conclusions 288
References 288
Efficient Preconditioner Updates for Semilinear Space–Time Fractional Reaction–Diffusion Equations 290
1 Introduction and Rationale 291
2 Fractional Linear Multistep Formulas or FLMMs 292
3 Preconditioning the Linear Systems of the Newton Iterations 295
4 Numerical Experiments 299
4.1 A Time-Fractional Biological Population Model 299
References 306
A Nuclear-Norm Model for Multi-Frame Super-Resolution Reconstruction from Video Clips 308
1 Introduction 308
2 Low-Resolution Model with Shifts 311
3 Nuclear-Norm Model 312
3.1 Decomposition of the Warping Matrices 313
3.2 Algorithm for Solving the Nuclear-Norm Model 315
3.3 Image Registration and Parameter Selection 316
4 Numerical Experiments 318
4.1 Synthetic Videos 319
4.2 Real Videos 322
5 Conclusion 326
References 326