Matrix Computations and Semiseparable Matrices: Eigenvalue and Singular Value Methods

Contents......Page 6
Preface......Page 12
Notation......Page 16
1 Introduction to semiseparable matrices......Page 18
1.1 Definition of semiseparable matrices......Page 19
1.2.1 Relations under inversion......Page 22
1.2.2 Generator representable semiseparable matrices......Page 24
1.3.1 The generator representation......Page 27
1.3.2 The Givens-vector representation......Page 28
1.4 Conclusions......Page 31
I: The reduction of matrices......Page 32
2 Algorithms for reducing matrices......Page 36
2.1 Introduction......Page 37
2.2 Orthogonal similarity transformations of symmetric matrices......Page 41
2.3 Orthogonal similarity transformation of (unsymmetric) matrices......Page 58
2.4 Orthogonal transformations of matrices......Page 61
2.5 Transformations from sparse to structured rank form......Page 72
2.6 From structured rank to sparse form......Page 73
2.7 Conclusions......Page 82
3 Convergence properties of the reduction algorithms......Page 84
3.1 The Arnoldi(Lanczos)-Ritz values......Page 85
3.2 Subspace iteration inside the reduction algorithms......Page 98
3.3 Interaction of the convergence behaviors......Page 116
3.4 Conclusions......Page 124
4 Implementation of the algorithms and numerical experiments......Page 126
4.1 Working with Givens transformations......Page 127
4.2 Implementation details......Page 139
4.3 Numerical experiments......Page 149
4.4 Conclusions......Page 165
II: QR-algorithms (eigenvalue problems)......Page 166
5 Introduction: traditional sparse QR-algorithms......Page 172
5.1 On the QR-algorithm......Page 173
5.2 A QR-algorithm for sparse matrices......Page 177
5.3 An implicit QR-method for sparse matrices......Page 180
5.4 On computing the singular values......Page 184
5.5 Conclusions......Page 187
6 Theoretical results for structured rank QR-algorithms......Page 188
6.1 Preserving the structure under a QR-step......Page 190
6.2 An implicit Q-theorem......Page 199
6.3 On Hessenberg-like plus diagonal matrices......Page 211
6.4 Conclusions......Page 215
7 Implicit QR-methods for semiseparable matrices......Page 216
7.1 An implicit QR-algorithm for symmetric semiseparable matrices......Page 217
7.2 A QR-algorithm for semiseparable plus diagonal......Page 235
7.3 An implicit QR-algorithm for Hessenberg-like matrices......Page 239
7.4 An implicit QR-algorithm for computing the singular values......Page 246
7.5 Conclusions......Page 254
8 Implementation and numerical experiments......Page 256
8.1 Working with Givens transformations......Page 258
8.2 Implementation of the QR-algorithm for semiseparable matrices......Page 276
8.3 Computing the eigenvectors......Page 281
8.4 Numerical experiments......Page 287
8.5 Conclusions......Page 292
9 More on QR-related algorithms......Page 294
9.1 Complex arithmetic and Givens transformations......Page 296
9.2 Variations of the QR-algorithm......Page 297
9.3 The QR-method for quasiseparable matrices......Page 307
9.4 The multishift QR-algorithm......Page 316
9.5 A QH-algorithm......Page 330
9.6 Computing zeros of polynomials......Page 344
9.7 References to related subjects......Page 371
9.8 Conclusions......Page 378
III: Some generalizations and miscellaneous topics......Page 380
10 Divide-and-conquer algorithms for the eigendecomposition......Page 384
10.1 Arrowhead and diagonal plus rank 1 matrices......Page 385
10.2 Divide-and-conquer algorithms for tridiagonal matrices......Page 392
10.3 Divide-and-conquer methods for quasiseparable matrices......Page 395
10.4 Computational complexity and numerical experiments......Page 404
10.5 Conclusions......Page 408
11 A Lanczos-type algorithm and rank revealing......Page 410
11.1 Lanczos semiseparabilization......Page 411
11.2 Rank-revealing properties of the orthogonal similarity reduction......Page 421
11.3 Conclusions......Page 427
IV: Orthogonal (rational) functions (Inverse eigenvalue problems)......Page 428
12 Orthogonal polynomials and discrete least squares......Page 432
12.1 Recurrence relation and Hessenberg matrix......Page 433
12.2 Discrete inner product......Page 434
12.3 Inverse eigenvalue problem......Page 435
12.4 Polynomial least squares approximation......Page 437
12.5 Updating algorithm......Page 438
12.6 Special cases......Page 440
12.7 Conclusions......Page 444
13.1 Vector approximants......Page 446
13.2 Equal degrees......Page 448
13.3 Arbitrary degrees......Page 453
13.4 The singular case......Page 459
13.5 Conclusions......Page 462
14 Orthogonal rational functions......Page 464
14.1 The computation of orthonormal rational functions......Page 466
14.2 Solving the inverse eigenvalue problem......Page 471
14.3 Special configurations of points z[sub(i)]......Page 475
14.4 Conclusions......Page 483
15.1 Software......Page 484
15.2 Conclusions......Page 485
Bibliography......Page 488
D......Page 504
G......Page 505
P......Page 506
V......Page 507
Z......Page 508
D......Page 509
I......Page 510
O......Page 511
Q......Page 512
S......Page 513
U......Page 514
Z......Page 515