Matrix Computations and Semiseparable Matrices, Volume 1: Linear Systems

Contents......Page 6
Preface......Page 14
Notation......Page 18
I: Introduction to semiseparable and related matrices......Page 20
1 Semiseparable and related matrices: definitions and properties......Page 24
1.1 Symmetric semiseparable and related matrices......Page 26
1.2 Relations between the different symmetric definitions......Page 31
1.3 Unsymmetric semiseparable and related matrices......Page 47
1.4 Relations between the different “unsymmetric” definitions......Page 50
1.5 Relations under inversion......Page 56
1.6 Conclusions......Page 69
2 The representation of semiseparable and related matrices......Page 72
2.1 Representations......Page 74
2.2 The symmetric generator representation......Page 78
2.3 The symmetric diagonal-subdiagonal representation......Page 84
2.4 The symmetric Givens-vector representation......Page 90
2.5 The symmetric quasiseparable representation......Page 98
2.6 Some examples......Page 101
2.7 The unsymmetric generator representation......Page 103
2.8 The unsymmetric Givens-vector representation......Page 109
2.9 The unsymmetric quasiseparable representation......Page 111
2.10 The decoupled representation for semiseparable matrices......Page 112
2.11 Summary of the representations......Page 114
2.12 Are there more representations?......Page 116
2.13 Some algorithms related to representations......Page 117
2.14 Conclusions......Page 125
3 Historical applications and other topics......Page 128
3.1 Oscillation matrices......Page 129
3.2 Semiseparable matrices as covariance matrices......Page 142
3.3 Discretization of integral equations......Page 149
3.4 Orthogonal rational functions......Page 152
3.5 Some comments......Page 153
3.6 Conclusions......Page 160
II: Linear systems with semiseparable and related matrices......Page 162
4 Gaussian elimination......Page 168
4.1 About Gaussian elimination and the LU-factorization......Page 170
4.2 Backward substitution......Page 171
4.3 Inversion of triangular semiseparable matrices......Page 172
4.4 Theoretical considerations of the LU-decomposition......Page 178
4.5 The LU-decomposition for semiseparable matrices......Page 182
4.6 The LU-decomposition for quasiseparable matrices......Page 190
4.7 Some comments......Page 197
4.8 Conclusions......Page 198
5 The QR-factorization......Page 200
5.1 About the QR-decomposition......Page 201
5.2 Theoretical considerations of the QR-decomposition......Page 202
5.3 A QR-factorization of semiseparable matrices......Page 205
5.4 A QR-factorization of quasiseparable matrices......Page 211
5.5 Implementing the QR-factorization......Page 213
5.6 Other decompositions......Page 218
5.7 Conclusions......Page 223
6 A Levinson-like and Schur-like solver......Page 224
6.1 About the Levinson algorithm......Page 225
6.2 Generator representable semiseparable plus diagonal matrices......Page 229
6.3 A Levinson framework......Page 238
6.4 Examples......Page 253
6.5 The Schur algorithm......Page 264
6.6 Conclusions......Page 275
7 Inverting semiseparable and related matrices......Page 276
7.1 Known factorizations......Page 277
7.2 Direct inversion methods......Page 280
7.3 General formulas for inversion......Page 293
7.4 Scaling of symmetric positive definite semiseparable matrices......Page 296
7.5 Decay rates for the inverses of tridiagonal matrices......Page 297
7.6 Conclusions......Page 304
III: Structured rank matrices......Page 306
8 Definitions of higher order semiseparable matrices......Page 312
8.1 Structured rank matrices......Page 313
8.2 Definition of higher order semiseparable and related matrices......Page 317
8.3 Inverses of structured rank matrices......Page 329
8.4 Generator representable semiseparable matrices......Page 337
8.5 Representations......Page 361
8.6 Conclusions......Page 364
9 A QR-factorization for structured rank matrices......Page 366
9.1 A sequence of Givens transformations from bottom to top......Page 369
9.2 Making the structured rank matrix upper triangular......Page 398
9.3 Different patterns of annihilation......Page 406
9.4 Rank-expanding sequences of Givens transformations......Page 419
9.5 QR-factorization for the Givens-vector representation......Page 435
9.6 Extra material......Page 444
9.7 Multiplication between structured rank matrices......Page 449
9.8 Conclusions......Page 452
10 A Gauss solver for higher order structured rank systems......Page 454
10.1 A sequence of Gauss transformation matrices without pivoting......Page 456
10.2 Effect of pivoting on rank structures......Page 467
10.3 More on sequences of Gauss transforms......Page 473
10.4 Solving systems with Gauss transforms......Page 475
10.5 Different patterns of annihilation......Page 480
10.6 Conclusions......Page 489
11 A Levinson-like solver for structured rank matrices......Page 492
11.1 Higher order generator representable semiseparable matrices......Page 493
11.2 General quasiseparable matrices......Page 494
11.3 Band matrices......Page 495
11.5 Summations of Levinson-conform matrices......Page 497
11.6 Conclusions......Page 498
12.1 Definition......Page 500
12.2 Factorization of the block lower/upper triangular part......Page 501
12.3 Connection to structured rank matrices......Page 502
12.5 Multiplication of a block quasiseparable matrix by a vector......Page 503
12.6 Solver for block quasiseparable systems......Page 504
12.7 Block quasiseparable matrices and descriptor systems......Page 506
12.8 Conclusions......Page 509
13.1 H-matrices or hierarchical matrices......Page 510
13.3 Hierarchically semiseparable matrices......Page 514
13.4 Other classes of structured rank matrices......Page 515
13.5 Conclusions......Page 516
14 Inversion of structured rank matrices......Page 518
14.1 Banded Toeplitz matrices......Page 519
14.2 Inversion of (generalized) Hessenberg matrices......Page 530
14.3 Inversion of higher order semiseparable and band matrices......Page 534
14.4 Block matrices......Page 540
14.5 Quasiseparable matrices......Page 544
14.6 Generalized inverses......Page 546
14.7 Conclusions......Page 548
15.1 Software......Page 550
15.2 Conclusions......Page 551
Bibliography......Page 552
C......Page 576
G......Page 577
J......Page 578
M......Page 579
R......Page 580
V......Page 581
Z......Page 582
C......Page 584
G......Page 585
H......Page 586
L......Page 587
M......Page 588
P......Page 589
R......Page 590
S......Page 591
Y......Page 593
Z......Page 594