Table of contents for Matrix computations and semiseparable matrices / Raf Vandebril, Marc Van Barel, Nicola Mastronardi.

Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.


Counter
Contents
On the cover v
Abstract vii
Preface xvii
Notation xxi
I Introduction to semiseparable and related matrices 1
1 Semiseparable and related matrices, de_nitions and properties 5
1.1 Symmetric semiseparable and related matrices. . . . . . . . . . 7
1.2 Relations between the di_erent symmetric de_nitions. . . . . . 12
1.2.1 Known relations. . . . . . . . . . . . . . . . . . . . 12
1.2.2 Common misunderstandings. . . . . . . . . . . . . 13
1.2.3 A theoretical problem, with numerical consequences 14
1.2.4 Generator representable semiseparable. . . . . . . . 16
1.2.5 Semiseparable plus diagonal and quasiseparable . . 21
1.2.6 Summary of the relations. . . . . . . . . . . . . . . 25
1.2.7 More on the pointwise convergence. . . . . . . . . . 25
1.3 Unsymmetric semiseparable and related matrices. . . . . . . . 27
1.4 Relations between the di_erent `unsymmetric' de_nitions. . . . 30
1.4.1 Extension of known symmetric relations. . . . . . . 30
1.4.2 Symmetric rank structures. . . . . . . . . . . . . . 33
1.4.3 Summary of the relations. . . . . . . . . . . . . . . 36
1.5 Relations under inversion. . . . . . . . . . . . . . . . . . . . . . 36
1.5.1 The nullity theorem. . . . . . . . . . . . . . . . . . 37
1.5.2 The inverse of a semiseparable matrix. . . . . . . . 40
1.5.3 The inverse of a quasiseparable matrix. . . . . . . . 42
1.5.4 The inverse of a semiseparable plus diagonal matrix 44
1.5.5 Summary of the relations. . . . . . . . . . . . . . . 46
1.6 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2 The representation of semiseparable and related matrices 51
ix
x Contents
2.1 Representations. . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.1.1 The de_nition of a representation. . . . . . . . . . 54
2.1.2 A representation is `just' a representation. . . . . . 55
2.1.3 Covered representations. . . . . . . . . . . . . . . . 56
2.2 The symmetric generator representation. . . . . . . . . . . . . 57
2.2.1 The representation for symmetric semiseparables . . 57
2.2.2 Application to other classes of matrices. . . . . . . 60
2.3 The symmetric diagonal-subdiagonal representation. . . . . . . 63
2.3.1 The representation for symmetric semiseparables . . 63
2.3.2 The representation for symmetric quasiseparables . 66
2.4 The symmetric Givens-vector representation. . . . . . . . . . . 69
2.4.1 The representation for symmetric semiseparables . . 69
2.4.2 Examples. . . . . . . . . . . . . . . . . . . . . . . . 71
2.4.3 Retrieving the Givens-vector representation. . . . . 72
2.4.4 Swapping the representation. . . . . . . . . . . . . 75
2.4.5 Application to other classes of matrices. . . . . . . 76
2.5 The symmetric quasiseparable representation. . . . . . . . . . . 77
2.5.1 The representation for symmetric semiseparables . . 77
2.5.2 Application to other classes matrices. . . . . . . . . 79
2.6 Some examples. . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.7 The unsymmetric generator representation. . . . . . . . . . . . 81
2.7.1 The representation for semiseparables. . . . . . . . 82
2.7.2 Application to other classes of matrices. . . . . . . 85
2.8 The unsymmetric Givens-vector representation. . . . . . . . . . 88
2.8.1 The representation for semiseparables. . . . . . . . 88
2.8.2 Application to other classes of matrices. . . . . . . 89
2.9 The unsymmetric quasiseparable representation. . . . . . . . . 89
2.9.1 The representation for semiseparables. . . . . . . . 89
2.9.2 Application to other classes of matrices. . . . . . . 90
2.10 The decoupled representation for semiseparable matrices. . . . 91
2.10.1 The decoupled generator representation. . . . . . . 91
2.10.2 The decoupled Givens-vector representation. . . . . 92
2.11 Summary of the representations. . . . . . . . . . . . . . . . . . 93
2.12 Are there more representations?. . . . . . . . . . . . . . . . . . 94
2.13 Some algorithms related to representations. . . . . . . . . . . . 95
2.13.1 A fast matrix vector multiplication. . . . . . . . . . 95
2.13.2 Changing representations. . . . . . . . . . . . . . . 98
2.13.3 Computing the determinant in O(n) ops. . . . . . 101
2.14 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3 Historical applications and other topics 105
3.1 Oscillation matrices. . . . . . . . . . . . . . . . . . . . . . . . . 106
3.1.1 Introduction. . . . . . . . . . . . . . . . . . . . . . 107
3.1.2 De_nition and examples. . . . . . . . . . . . . . . . 109
3.1.3 The inverse of a one-pair matrix. . . . . . . . . . . 112
3.1.4 The example of the one-pair matrix. . . . . . . . . 116
Contents xi
3.1.5 Some other interesting applications. . . . . . . . . . 117
3.1.6 The connection with eigenvalues and eigenvectors . 117
3.2 Semiseparable matrices as covariance matrices. . . . . . . . . . 119
3.2.1 Covariance calculations. . . . . . . . . . . . . . . . 119
3.2.2 The multinomial distribution. . . . . . . . . . . . . 120
3.2.3 Some other matrices. . . . . . . . . . . . . . . . . . 124
3.3 Discretization of integral equations. . . . . . . . . . . . . . . . 126
3.4 Orthogonal rational functions. . . . . . . . . . . . . . . . . . . 128
3.5 Some comments. . . . . . . . . . . . . . . . . . . . . . . . . . . 130
3.5.1 The name `semiseparable' matrix. . . . . . . . . . . 130
3.5.2 Eigenvalue problems. . . . . . . . . . . . . . . . . . 131
3.5.3 References to applications. . . . . . . . . . . . . . . 135
3.6 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
II Linear systems with semiseparable and related matrices 137
4 Gaussian elimination 143
4.1 About Gaussian elimination and the LU-factorization. . . . . . 145
4.2 Backward substitution. . . . . . . . . . . . . . . . . . . . . . . 146
4.3 Inversion of triangular semiseparable matrices. . . . . . . . . . 147
4.3.1 The inverse of a bidiagonal. . . . . . . . . . . . . . 148
4.3.2 The inverse of lower semiseparable matrices. . . . . 150
4.3.3 Examples. . . . . . . . . . . . . . . . . . . . . . . . 151
4.4 Theoretical considerations of the LU-decomposition. . . . . . . 153
4.5 The LU-decomposition for semiseparable matrices. . . . . . . . 156
4.5.1 Strongly nonsingular matrices. . . . . . . . . . . . . 157
4.5.2 General semiseparable matrices. . . . . . . . . . . . 159
4.6 The LU-decomposition for quasiseparable matrices. . . . . . . 164
4.6.1 A _rst naive factorization scheme. . . . . . . . . . . 165
4.6.2 The strongly nonsingular case, without pivoting . . 168
4.6.3 The strongly nonsingular case. . . . . . . . . . . . . 170
4.7 Some comments. . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.7.1 Numerical stability. . . . . . . . . . . . . . . . . . . 172
4.7.2 A representation?. . . . . . . . . . . . . . . . . . . 173
4.8 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
5 The QR-factorization 175
5.1 About the QR-decomposition. . . . . . . . . . . . . . . . . . . 176
5.2 Theoretical considerations of the QR-decomposition. . . . . . . 177
5.3 A QR-factorization of semiseparable matrices. . . . . . . . . . 180
5.3.1 The factorization using Givens transformations . . . 180
5.3.2 The generators of the factors. . . . . . . . . . . . . 182
5.3.3 The Givens-vector representation. . . . . . . . . . . 185
5.3.4 Solving systems of equations. . . . . . . . . . . . . 185
5.4 A QR-factorization of quasiseparable matrices. . . . . . . . . . 186
xii Contents
5.5 An implementation. . . . . . . . . . . . . . . . . . . . . . . . . 188
5.6 Other decompositions. . . . . . . . . . . . . . . . . . . . . . . . 192
5.6.1 The URV-decomposition. . . . . . . . . . . . . . . 193
5.6.2 Some other orthogonal decompositions. . . . . . . . 195
5.7 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
6 A Levinson-like and Schur-like solver 199
6.1 About the Levinson algorithm. . . . . . . . . . . . . . . . . . . 200
6.1.1 The Yule-Walker problem and the Durbin algorithm 201
6.1.2 The Levinson algorithm. . . . . . . . . . . . . . . . 202
6.1.3 An upper triangular factorization of the inverse . . . 203
6.2 Generator representable semiseparable plus diagonal matrices . 204
6.2.1 The class of matrices. . . . . . . . . . . . . . . . . . 204
6.2.2 A Yule-Walker-like problem. . . . . . . . . . . . . . 205
6.2.3 A Levinson-type algorithm. . . . . . . . . . . . . . 209
6.2.4 An upper triangular factorization of the inverse . . . 212
6.2.5 Some general remarks. . . . . . . . . . . . . . . . . 213
6.3 A Levinson Framework. . . . . . . . . . . . . . . . . . . . . . . 213
6.3.1 The matrix block decomposition. . . . . . . . . . . 214
6.3.2 A framework. . . . . . . . . . . . . . . . . . . . . . 215
6.3.3 An upper triangular factorization. . . . . . . . . . . 225
6.3.4 The look-ahead procedure. . . . . . . . . . . . . . . 226
6.4 Examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
6.4.1 Givens-vector represented semiseparable matrices . . 228
6.4.2 Quasiseparable matrices. . . . . . . . . . . . . . . . 229
6.4.3 Tridiagonal matrices. . . . . . . . . . . . . . . . . . 230
6.4.4 Arrowhead matrices. . . . . . . . . . . . . . . . . . 231
6.4.5 Unsymmetric structures. . . . . . . . . . . . . . . . 233
6.4.6 Upper triangular matrices. . . . . . . . . . . . . . . 233
6.4.7 Dense matrices. . . . . . . . . . . . . . . . . . . . . 234
6.4.8 Summations of Levinson-conform matrices. . . . . 234
6.4.9 Matrices with errors in structures. . . . . . . . . . 235
6.4.10 Companion matrices. . . . . . . . . . . . . . . . . . 236
6.4.11 Comrade matrix. . . . . . . . . . . . . . . . . . . . 237
6.4.12 Fellow matrices. . . . . . . . . . . . . . . . . . . . . 238
6.5 About the Schur algorithm. . . . . . . . . . . . . . . . . . . . . 239
6.6 The Schur complement. . . . . . . . . . . . . . . . . . . . . . . 239
6.7 Displacement rank of Toeplitz{structured matrices. . . . . . . 240
6.8 The Schur reduction. . . . . . . . . . . . . . . . . . . . . . . . . 241
6.8.1 Schur reduction for quasiseparable matrices. . . . . 242
6.8.2 Schur-like algorithm for quasiseparable matrices . . 244
6.9 A more general framework for the Schur reduction. . . . . . . . 247
6.10 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
7 Inverting semiseparable and related matrices 251
7.1 Known factorizations. . . . . . . . . . . . . . . . . . . . . . . . 252
Contents xiii
7.1.1 Inversion via the QR-factorization. . . . . . . . . . 252
7.1.2 Inversion via the LU-factorization. . . . . . . . . . 253
7.1.3 Inversion via the Levinson-algorithm. . . . . . . . . 253
7.2 Direct inversion methods. . . . . . . . . . . . . . . . . . . . . . 255
7.2.1 The inverse of a symmetric tridiagonal matrix . . . 255
7.2.2 The inverse of a symmetric semiseparable matrix . . 258
7.2.3 The inverse of a tridiagonal matrix. . . . . . . . . . 260
7.2.4 The inverse of a speci_c semiseparable matrix. . . . 265
7.3 General formulas for inversion. . . . . . . . . . . . . . . . . . . 267
7.4 Scaling semiseparable matrices. . . . . . . . . . . . . . . . . . . 270
7.5 Bounds on the size of the elements of the inverse. . . . . . . . . 271
7.5.1 M-matrices. . . . . . . . . . . . . . . . . . . . . . . 271
7.5.2 Diagonally dominant tridiagonal M-matrices. . . . 272
7.5.3 Diagonally dominant tridiagonal matrices. . . . . . 274
7.6 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
III Structured rank matrices 279
8 De_nitions of higher order semiseparable matrices 285
8.1 Structured rank matrices. . . . . . . . . . . . . . . . . . . . . . 286
8.2 De_nition of higher order semiseparable and related matrices. . 289
8.2.1 Some inner structured rank relations. . . . . . . . . 290
8.2.2 Higher order semiseparable matrices. . . . . . . . . 291
8.2.3 Higher order quasiseparable matrices. . . . . . . . . 293
8.2.4 Higher order generator representable. . . . . . . . . 294
8.2.5 Extended semiseparable matrices. . . . . . . . . . . 296
8.2.6 Hessenberg-like matrices. . . . . . . . . . . . . . . . 297
8.2.7 Sparse matrices. . . . . . . . . . . . . . . . . . . . . 298
8.2.8 What is in a name. . . . . . . . . . . . . . . . . . . 299
8.3 Inverses of structured rank matrices. . . . . . . . . . . . . . . . 301
8.3.1 Inverse of structured rank matrices. . . . . . . . . . 302
8.3.2 Some particular inverses. . . . . . . . . . . . . . . . 307
8.4 Generator representable semiseparable matrices. . . . . . . . . 309
8.4.1 Generator representation. . . . . . . . . . . . . . . 309
8.4.2 When is a matrix generator representable?. . . . . 311
8.4.3 Decomposition of structured rank matrices. . . . . 319
8.4.4 Examples of the decomposition. . . . . . . . . . . . 329
8.5 Representations. . . . . . . . . . . . . . . . . . . . . . . . . . . 333
8.5.1 Givens-vector representation. . . . . . . . . . . . . 333
8.5.2 Quasiseparable representation. . . . . . . . . . . . . 333
8.5.3 Split representations. . . . . . . . . . . . . . . . . . 334
8.6 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
9 A QR-factorization for structured rank matrices 337
9.1 A sequence of Givens transformations from bottom to top . . . 340
xiv Contents
9.1.1 Annihilating lower rank 1 structures. . . . . . . . . 341
9.1.2 Performed on lower rank 1 structures. . . . . . . . 344
9.1.3 Givens transformations on lower rank structures . . 346
9.1.4 Can the value of p in _(p)
l be larger than 1. . . . . 350
9.1.5 Givens transformations on upper rank 1 structures . 352
9.1.6 Givens transformations on upper rank structures . . 357
9.1.7 Givens transformations on rank structures. . . . . . 359
9.1.8 Other directions of sequences of transformations . . 362
9.1.9 Examples. . . . . . . . . . . . . . . . . . . . . . . . 365
9.1.10 Summary. . . . . . . . . . . . . . . . . . . . . . . . 368
9.2 Making the structured rank matrix upper triangular. . . . . . . 370
9.2.1 Annihilating completely the rank structure. . . . . 370
9.2.2 Expanding the zero rank structure. . . . . . . . . . 371
9.2.3 Combination of up going and descending sequences . 371
9.2.4 Examples. . . . . . . . . . . . . . . . . . . . . . . . 373
9.2.5 Solving systems of equations. . . . . . . . . . . . . 376
9.2.6 Other decompositions. . . . . . . . . . . . . . . . . 376
9.3 Di_erent patterns of annihilation. . . . . . . . . . . . . . . . . 377
9.3.1 The leaf form for removing the rank structure . . . 378
9.3.2 The pyramid form for removing the rank structure . 379
9.3.3 The leaf form for creating zeros. . . . . . . . . . . . 381
9.3.4 The diamond form for creating zeros. . . . . . . . . 381
9.3.5 Theorems connected to Givens transformations . . . 382
9.3.6 The ^-pattern. . . . . . . . . . . . . . . . . . . . . 385
9.3.7 The "-pattern. . . . . . . . . . . . . . . . . . . . . 385
9.3.8 The _-pattern. . . . . . . . . . . . . . . . . . . . . 386
9.3.9 Givens transformations in the _-pattern. . . . . . . 387
9.4 Rank expanding sequences of Givens transformations. . . . . . 390
9.4.1 The Givens transformation. . . . . . . . . . . . . . 390
9.4.2 Rank expanding on upper rank 1 structures. . . . . 392
9.4.3 Existence and the e_ect on upper rank structures . 395
9.4.4 Global theorem for sequences from bottom to top . 405
9.5 QR-factorization for the Givens-vector representation. . . . . . 406
9.5.1 The Givens-vector representation. . . . . . . . . . . 406
9.5.2 Applying sequences of transformations. . . . . . . . 408
9.5.3 Computing the rank expanding Givens. . . . . . . 410
9.6 Extra material. . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
9.6.1 A general rank expanding QR-factorization. . . . . 415
9.6.2 Parallel factorization. . . . . . . . . . . . . . . . . . 416
9.6.3 QZ-factorization of an unstructured matrix. . . . . 419
9.7 Multiplication between structured rank matrices. . . . . . . . . 421
9.7.1 Products of structured rank matrices. . . . . . . . 421
9.7.2 Examples. . . . . . . . . . . . . . . . . . . . . . . . 422
9.8 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
10 A Gauss-solver for higher order structured rank systems 425
Contents xv
10.1 A sequence of Gauss transforms without pivoting. . . . . . . . 427
10.1.1 Annihilating lower rank q structures. . . . . . . . . 427
10.1.2 Arbitrary transforms on lower rank structures . . . 430
10.1.3 Gauss transforms on upper rank structures. . . . . 432
10.1.4 A sequence of transforms from bottom to top. . . . 433
10.1.5 Up going and descending Gauss transforms. . . . . 434
10.1.6 Zero creating Gauss transforms. . . . . . . . . . . . 435
10.1.7 Rank expanding Gauss transforms. . . . . . . . . . 436
10.1.8 A sequence of Gauss transforms from top to bottom 438
10.2 E_ect of pivoting on rank structures. . . . . . . . . . . . . . . . 438
10.2.1 The e_ect of pivoting on the rank structure. . . . . 439
10.2.2 Combining Gauss transforms with pivoting. . . . . 441
10.2.3 Sequences of transformations involving pivoting . . . 442
10.2.4 Numerical stability. . . . . . . . . . . . . . . . . . . 444
10.3 More on sequences of Gauss transforms. . . . . . . . . . . . . . 444
10.3.1 Upper triangular Gauss transforms. . . . . . . . . . 444
10.3.2 Transformations on the right of the matrix. . . . . 445
10.4 Solving systems with Gauss transforms. . . . . . . . . . . . . . 446
10.4.1 Making the structured rank matrix upper triangular 446
10.4.2 Gauss solver and the LU-factorization. . . . . . . . 448
10.4.3 Other decompositions. . . . . . . . . . . . . . . . . 449
10.5 Di_erent patterns of annihilation. . . . . . . . . . . . . . . . . 451
10.5.1 The graphical representation. . . . . . . . . . . . . 452
10.5.2 Some standard patterns. . . . . . . . . . . . . . . . 453
10.5.3 Some theorems connected to Gauss transforms . . . 455
10.6 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
11 A Levinson-like solver for structured rank matrices 463
11.1 Higher order generator representable semiseparable matrices . . 464
11.2 General quasiseparable matrices. . . . . . . . . . . . . . . . . . 465
11.3 Band matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
11.4 Unsymmetric structures. . . . . . . . . . . . . . . . . . . . . . . 468
11.5 Summations of Levinson-conform matrices. . . . . . . . . . . . 468
11.6 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
12 Block quasiseparable matrices 471
12.1 De_nition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
12.2 Factorization of the block lower/upper part. . . . . . . . . . . . 472
12.3 Connection to structured rank matrices. . . . . . . . . . . . . . 473
12.4 Special cases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
12.5 Multiplication of a block quasiseparable matrix by a vector . . . 474
12.6 Solver for block quasiseparable systems. . . . . . . . . . . . . . 475
12.7 Block quasiseparable matrices and descriptor systems. . . . . . 477
12.8 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
13 H, H2 and hierarchically semiseparable matrices 481
xvi Contents
13.1 H-matrices or hierarchical matrices. . . . . . . . . . . . . . . . 481
13.2 H2-matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
13.3 Hierarchically semiseparable matrices. . . . . . . . . . . . . . . 485
13.4 Other classes of structured rank matrices. . . . . . . . . . . . . 486
13.5 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
14 Inversion of structured rank matrices 489
14.1 Banded Toeplitz matrices. . . . . . . . . . . . . . . . . . . . . . 490
14.2 Inversion of (generalized) Hessenberg matrices. . . . . . . . . . 501
14.3 Inversion of higher order semiseparable and band matrices. . . . 505
14.3.1 Generator representable semiseparable. . . . . . . . 505
14.3.2 Semiseparable. . . . . . . . . . . . . . . . . . . . . 509
14.4 Block matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
14.5 Quasiseparable matrices. . . . . . . . . . . . . . . . . . . . . . 515
14.6 Generalized inverses. . . . . . . . . . . . . . . . . . . . . . . . . 517
14.7 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
15 Concluding remarks & Software 519
15.1 Software. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
15.2 Conclusions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
Bibliography 521
Author/Editor Index 545
Index 553

Library of Congress Subject Headings for this publication:

Semiseparable matrices.
Matrices -- Data processing.
Numerical analysis.