Matrix Computations and Semiseparable Matrices

by Vandebril, Raf; Van Barel, Marc; Mastronardi, Nicola

• ISBN13: 9780801890529
• ISBN10: 0801890527
• Format: Hardcover
• Copyright: 2008-11-12
• Publisher: Johns Hopkins Univ Pr

Summary

The general properties and mathematical structures of semiseparable matrices were presented in volume 1 of Matrix Computations and Semiseparable Matrices. In volume 2, Raf Vandebril, Marc Van Barel, and Nicola Mastronardi discuss the theory of structured eigenvalue and singular value computations for semiseparable matrices. These matrices have hidden properties that allow the development of efficient methods and algorithms to accurately compute the matrix eigenvalues.This thorough analysis of semiseparable matrices explains their theoretical underpinnings and contains a wealth of information on implementing them in practice. Many of the routines featured are coded in Matlab and can be downloaded from the Web for further exploration.

Author Biography

Raf Vandebril is a researcher in the Department of Computer Science at the Catholic University of Leuven, Belgium. Marc Van Barel is a professor of computer science at the Catholic University of Leuven, Belgium. Nicola Mastronardi is a researcher at the M. Picone Institute for Applied Mathematics, Bari, Italy.

Table of Contents

Preface	p. xi
Notation	p. xv
Introduction to semiseparable matrices	p. 1
Definition of semiseparable matrices	p. 2
Some properties	p. 5
Relations under inversion	p. 5
Generator representable semiseparable matrices	p. 7
The representations	p. 10
The generator representation	p. 10
The Givens-vector representation	p. 11
Conclusions	p. 14
The reduction of matrices	p. 15
Algorithms for reducing matrices	p. 19
Introduction	p. 20
Equivalence transformations	p. 20
Orthogonal transformations	p. 21
Orthogonal similarity transformations of symmetric matrices	p. 24
To tridiagonal form	p. 24
To semiseparable form	p. 27
To semiseparable plus diagonal form	p. 33
Orthogonal similarity transformation of (unsymmetric) matrices	p. 41
To Hessenberg form	p. 41
To Hessenberg-like form	p. 43
To Hessenberg-like plus diagonal form	p. 44
Orthogonal transformations of matrices	p. 44
To upper (lower) bidiagonal form	p. 44
To upper (lower) triangular semiseparable form	p. 48
Relation with the reduction to semiseparable form	p. 53
Transformations from sparse to structured rank form	p. 55
From tridiagonal to semiseparable (plus diagonal)	p. 55
From bidiagonal to upper triangular semiseparable	p. 56
From structured rank to sparse form	p. 56
From semiseparable (plus diagonal) to tridiagonal	p. 57
From semiseparable to bidiagonal	p. 59
Conclusions	p. 65
Convergence properties of the reduction algorithms	p. 67
The Arnoldi(Lanczos)-Ritz values	p. 68
Ritz values and Arnoldi(Lanczos)-Ritz values	p. 69
The reduction to semiseparable form	p. 70
Necessary conditions to obtain the Ritz values	p. 71
Sufficient conditions to obtain the Ritz values	p. 73
The case of invariant subspaces	p. 75
Some general remarks	p. 78
The different reduction algorithms revisited	p. 78
Subspace iteration inside the reduction algorithms	p. 81
The reduction to semiseparable form	p. 81
The reduction to semiseparable plus diagonal form	p. 86
Nested multishift iteration	p. 88
The different reduction algorithms revisited	p. 95
Interaction of the convergence behaviors	p. 99
The reduction to semiseparable form	p. 99
The reduction to semiseparable plus diagonal form	p. 102
Convergence speed of the nested multishift iteration	p. 103
The other reduction algorithms	p. 107
Conclusions	p. 107
Implementation of the algorithms and numerical experiments	p. 109
Working with Givens transformations	p. 110
Graphical schemes	p. 110
Interaction of Givens transformations	p. 112
Updating the representation	p. 115
The reduction algorithm revisited	p. 118
Implementation details	p. 122
Reduction to symmetric semiseparable form	p. 123
Reduction to semiseparable plus diagonal form	p. 125
Reduction to Hessenberg-like	p. 125
Reduction to upper triangular semiseparable form	p. 126
Computational complexities of the algorithms	p. 128
Numerical experiments	p. 132
The reduction to semiseparable form	p. 132
The reduction to semiseparable plus diagonal form	p. 139
Conclusions	p. 148
QR-algorithms (eigenvalue problems)	p. 149
Introduction: traditional sparse QR-algorithms	p. 155
On the QR-algorithm	p. 156
The QR-factorization	p. 156
The QR-algorithm	p. 159
A QR-algorithm for sparse matrices	p. 160
The QR-factorization	p. 160
Maintaining the Hessenberg structure	p. 161
An implicit QR-method for sparse matrices	p. 163
An implicit QR-algorithm	p. 163
Bulge chasing	p. 164
The implicit Q-theorem	p. 167
On computing the singular values	p. 167
Conclusions	p. 170
Theoretical results for structured rank QR-algorithms	p. 171
Preserving the structure under a QR-step	p. 173
The QR-factorization	p. 174
A QR-step maintains the rank structure	p. 175
An implicit Q-theorem	p. 182
Unreduced Hessenberg-like matrices	p. 182
The reduction to unreduced Hessenberg-like form	p. 184
An implicit Q-theorem for Hessenberg-like matrices	p. 186
On Hessenberg-like plus diagonal matrices	p. 194
Conclusions	p. 198
Implicit QR-methods for semiseparable matrices	p. 199
An implicit QR-algorithm for symmetric semiseparable matrices	p. 200
Unreduced symmetric semiseparable matrices	p. 201
The shift [mu]	p. 205
An implicit QR-step	p. 205
Proof of the correctness of the implicit approach	p. 215
A QR-algorithm for semiseparable plus diagonal	p. 218
An implicit QR-algorithm for Hessenberg-like matrices	p. 222
The shift [mu]	p. 222
An implicit QR-step on the Hessenberg-like matrix	p. 223
Chasing the disturbance	p. 224
Proof of correctness	p. 229
An implicit QR-algorithm for computing the singular values	p. 229
Unreduced upper triangular semiseparable matrices	p. 230
An implicit QR-step	p. 231
Chasing the bulge	p. 233
Proof of correctness	p. 235
Conclusions	p. 237
Implementation and numerical experiments	p. 239
Working with Givens transformations	p. 241
Interaction of Givens transformations	p. 243
Graphical interpretation of a QR-step	p. 243
A QR-step for semiseparable plus diagonal matrices	p. 250
Implementation of the QR-algorithm for semiseparable matrices	p. 259
The QR-algorithm without shift	p. 259
The reduction to unreduced form	p. 260
The QR-algorithm with shift	p. 261
Deflation after a step of the QR-algorithm	p. 263
Computing the eigenvectors	p. 264
Computing all the eigenvectors	p. 264
Selected eigenvectors	p. 265
Preventing the loss of orthogonality	p. 266
The eigenvectors of an arbitrary symmetric matrix	p. 269
Numerical experiments	p. 270
On the symmetric eigenvalue solver	p. 270
Experiments for the singular value decomposition	p. 273
Conclusions	p. 275
More on QR-related algorithms	p. 277
Complex arithmetic and Givens transformations	p. 279
Variations of the QR-algorithm	p. 280
The QR-factorization and its variants	p. 280
Flexibility in the QR-algorithm	p. 284
The QR-algorithm and its variants	p. 287
The QR-method for quasiseparable matrices	p. 290
Definition and properties	p. 290
The QR-factorization and the QR-algorithm	p. 292
The implicit method	p. 294
The multishift QR-algorithm	p. 299
The multishift setting	p. 299
An efficient transformation from v to [plus or minus beta]e[subscript 1]	p. 300
The chasing method	p. 302
The real Hessenberg-like case	p. 312
A QH-algorithm	p. 313
More on the QH-factorization	p. 313
Convergence and preservation of the structure	p. 316
An implicit QH-iteration	p. 320
The QR-iteration is a disguised QH-iteration	p. 323
Numerical experiments	p. 325
Computing zeros of polynomials	p. 327
Connection to eigenproblems	p. 327
Unitary Hessenberg matrices	p. 333
Unitary plus rank 1 matrices	p. 338
Other methods	p. 348
References to related subjects	p. 354
Rational Krylov methods	p. 354
Sturm sequences	p. 356
Other references	p. 360
Conclusions	p. 361
Some generalizations and miscellaneous topics	p. 363
Divide-and-conquer algorithms for the eigendecomposition	p. 367
Arrowhead and diagonal plus rank 1 matrices	p. 368
Symmetric arrowhead matrices	p. 368
Computing the eigenvectors	p. 370
Rank 1 modification of a diagonal matrix	p. 371
Divide-and-conquer algorithms for tridiagonal matrices	p. 375
Transformation into a similar arrowhead matrix	p. 375
Transformation into a diagonal plus rank 1	p. 376
Divide-and-conquer methods for quasiseparable matrices	p. 378
A first divide-and-conquer algorithm	p. 379
A straightforward divide-and-conquer algorithm	p. 380
A one-way divide-and-conquer algorithm	p. 382
A two-way divide-and-conquer algorithm	p. 384
Computational complexity and numerical experiments	p. 387
Conclusions	p. 391
A Lanczos-type algorithm and rank revealing	p. 393
Lanczos semiseparabilization	p. 394
Lanczos reduction to tridiagonal form	p. 394
Lanczos reduction to semiseparable form	p. 395
Rank-revealing properties of the orthogonal similarity reduction	p. 404
Symmetric rank-revealing factorization	p. 404
Rank-revealing via the semiseparable reduction	p. 405
Numerical experiments	p. 407
Conclusions	p. 410
Orthogonal (rational) functions (Inverse eigenvalue problems)	p. 411
Orthogonal polynomials and discrete least squares	p. 415
Recurrence relation and Hessenberg matrix	p. 416
Discrete inner product	p. 417
Inverse eigenvalue problem	p. 418
Polynomial least squares approximation	p. 420
Updating algorithm	p. 421
Special cases	p. 423
Conclusions	p. 427
Orthonormal polynomial vectors	p. 429
Vector approximants	p. 429
Equal degrees	p. 431
The optimization problem	p. 431
The algorithm	p. 433
Summary	p. 436
Arbitrary degrees	p. 436
The problem	p. 436
The algorithm	p. 437
Orthogonal vector polynomials	p. 439
Solution of the general approximation problem	p. 441
The singular case	p. 442
Conclusions	p. 445
Orthogonal rational functions	p. 447
The computation of orthonormal rational functions	p. 449
The functional problem	p. 449
The inverse eigenvalue problem	p. 450
Recurrence relation for the columns of Q	p. 452
Recurrence relation for the orthonormal functions	p. 452
Solving the inverse eigenvalue problem	p. 454
Special configurations of points z[subscript i]	p. 458
Special case: all points z[subscript i] are real	p. 458
Special case: all points z[subscript i] lie on the unit circle	p. 459
Special case: all points z[subscript i] lie on a generic circle	p. 462
Conclusions	p. 466
Concluding remarks & software	p. 467
Software	p. 467
Conclusions	p. 468
Bibliography	p. 471
Author/Editor Index	p. 487
Subject Index	p. 492
Table of Contents provided by Ingram. All Rights Reserved.