Numerical Methods for Structured Matrices and Applications: The Georg Heinig Memorial Volume

Cover......Page 1
Operator Theory: Advances and Applications\rVol. 199......Page 3
Numerical Methods for\rStructured Matrices\rand Applications......Page 4
ISBN 9783764389956......Page 5
Table of Contents\r......Page 6
Foreword......Page 8
Part I: Georg Heinig......Page 11
Georg Heinig (1947–2005) In Memoriam......Page 13
Georg Heinig November 24, 1947 – May 10, 2005 A Personal Memoir and Appreciation......Page 17
List of Georg Heinig’s (refereed) publications......Page 22
Foreword......Page 35
1. Notation.......Page 40
3. Toeplitz, Hankel, and Toeplitz-plus-Hankel matrices.......Page 41
4. Quasi-Toeplitz matrices, quasi-Hankel matrices, and quasi-T+H matrices.......Page 42
5. Mobius transformations.......Page 43
1. Hankel Bezoutians.......Page 45
3. Uniqueness.......Page 48
4. Quasi-H-Bezoutians.......Page 49
6. Splitting of H-Bezoutians.......Page 50
7. Toeplitz Bezoutians.......Page 51
9. Symmetric and skewsymmetric T-Bezoutians.......Page 53
10. Hermitian T-Bezoutians.......Page 54
11. Splitting of symmetric T-Bezoutians.......Page 55
12. Relations between H- and T-Bezoutians.......Page 57
1. Kravitsky-Russakovsky formulas.......Page 58
2. Matrix representations of Bezoutians.......Page 59
3. Bezoutians as Schur complements.......Page 60
1. Inverses of Hankel matrices.......Page 61
4. Inverses of Toeplitz matrices.......Page 63
5. Characterization of fundamental systems.......Page 64
6. Inverses of symmetric Toeplitz matrices.......Page 66
7. Inverses of skewsymmetric Toeplitz matrices.......Page 67
8. Inverses of Hermitian Toeplitz matrices.......Page 68
2. Factorization step for H-Bezoutians.......Page 69
4. Generalized UL-factorization of H-Bezoutians.......Page 70
6. Factorization step for T-Bezoutians in the generic case.......Page 71
7. LU-factorization of T-Bezoutians.......Page 72
8. Non-generic case for T-Bezoutians.......Page 73
9. Hermitian T-Bezoutians.......Page 74
1. Factorization of the companion.......Page 75
2. Functional calculus.......Page 76
4. Barnett’s formula for T-Bezoutians.......Page 77
1. Generating functions of Hankel matrices.......Page 78
2. Vandermonde factorization of Hankel matrices.......Page 81
3.Real Hankel matrices.......Page 82
4. The Cauchy index.......Page 83
5. Congruence to H-Bezoutians.......Page 84
7. Solving the Bezout equation.......Page 86
1. Generating functions of Toeplitz matrices.......Page 87
2. Matrices with symmetry properties.......Page 89
3. Vandermonde factorization of nonsingular Toeplitz matrices.......Page 90
5. Signature and Cauchy index.......Page 91
6. Congruence to T-Bezoutians.......Page 92
7. Inverses of T-Bezoutians.......Page 93
9. Vandermonde reduction of Bezoutians......Page 94
1. Non-confluent Hankel case.......Page 95
2. Non-confluent Toeplitz case.......Page 96
3. Confluent case.......Page 97
2. Inertia with respect to the real line.......Page 99
3. Real roots of real polynomials.......Page 101
4. Inertia with respect to the imaginary axis.......Page 102
5. Roots on the imaginary axis and positive real roots of real polynomials.......Page 103
6. Inertia with respect to the unit circle.......Page 104
1. Definition.......Page 105
3. Uniqueness.......Page 106
4. Inverses of T+H-Bezoutians.......Page 108
1. Fundamental systems.......Page 109
2. Inversion of T+H matrices.......Page 110
3. Inversion of symmetric T+H matrices.......Page 113
4. Inversion of centrosymmetric T+H matrices.......Page 114
5. Inversion of centro-skewsymmetric T+H matrices.......Page 116
13. Exercises......Page 120
14. Notes......Page 123
References......Page 124
1. Introduction......Page 129
2. On a family of polynomials......Page 131
3. Appendix......Page 132
References......Page 133
A Traub-like Algorithm for Hessenberg quasiseparable-Vandermonde Matrices of Arbitrary Order......Page 137
1.2. Capturing recurrence relations via confederate matrices......Page 138
1.3. Main tool: quasiseparable matrices and polynomials......Page 141
1.4. Main problem: Inversion of (H,m)-quasiseparable-Vandermonde matrices......Page 142
2. Inversion formula......Page 143
2.1. The key property of all Traub-like algorithms: pertransposition......Page 144
3. Recurrence relations for (H,m)-quasiseparable polynomials......Page 146
3.1. Generators of quasiseparable matrices......Page 147
3.2. Sparse recurrence relations for (H,m)-quasiseparable polynomials......Page 148
4.1. Introduction of a perturbation term via pertransposition of confederate matrices......Page 150
4.2. Perturbed [EGO05]-type recurrence relations......Page 151
4.3. Known special cases of these more general recurrence relations......Page 153
5. Computing the coefficients of the master polynomial......Page 155
6.1. Quasiseparable generator input......Page 157
6.2. Recurrence relation coefficient input......Page 158
7. Numerical Experiments......Page 159
8. Conclusions......Page 160
References......Page 162
Part II: Research Contributions......Page 135
1. Introduction......Page 165
2.1. Sylvester and B´ezout matrices......Page 168
2.2. Cauchy-like matrices......Page 169
2.3. Modified GKO algorithm......Page 171
3.1. Estimating degree and coefficients of the  -gcd......Page 172
3.2. Refinement......Page 173
3.3. The overall algorithm......Page 176
4. Numerical experiments......Page 177
4.1. Badly conditioned polynomials......Page 178
4.2. High gcd degree......Page 179
4.5. Small leading coefficient......Page 180
4.6. Running time......Page 181
References......Page 182
1. Introduction......Page 185
2. The interior case......Page 188
3. The boundary case......Page 192
References......Page 199
1. Introduction......Page 201
2. H¨older continuity......Page 204
3. Counterexamples......Page 205
4. Sufficient conditions......Page 207
References......Page 211
1. Introduction......Page 213
1.1. Main definitions and notations......Page 215
1.2. Basic displacement structured matrices......Page 216
2. Cauchy matrices......Page 217
3. Vandermonde matrices......Page 218
3.1. Vandermonde matrices with nonnegative nodes......Page 222
3.2. Vandermonde matrices with symmetric nodes......Page 223
4. Cauchy-Vandermonde matrices......Page 225
References......Page 228
1. Introduction and background......Page 231
2. Auxiliary results......Page 233
3. QR decomposition of TN matrices......Page 234
4. Symmetric-triangular decomposition of TN matrices......Page 235
References......Page 237
1. Introduction......Page 239
2. Rank Structure Preliminaries......Page 241
3. QR-factorization of displacement structured matrices......Page 243
4. The Cauchy-like case......Page 248
5. The Vandermonde-like case......Page 257
6. The Toeplitz-like case......Page 258
7. Numerical experiments......Page 260
References......Page 263
1. Introduction......Page 265
2. The construction of hξ......Page 269
3. Bezoutians......Page 271
4. The matrix L for ν = 1 and indefinite Γ......Page 272
5. The unit circle case γ = T......Page 275
6. The imaginary axis case γ = iR......Page 278
7. Computation of hξ via its minimal realizations......Page 282
8. The construction of hη......Page 283
9. The limit behavior of Q......Page 285
10. Bilinear transformation between D and H......Page 288
11. Examples......Page 289
References......Page 296
0. Introduction......Page 299
1. Preliminaries......Page 301
2. On a parametrization of the solution set Cq[D, (Γj)nj=0]......Page 304
3. Particular matrix-valued Schur functions associated with given q × q Carath´eodory sequences......Page 307
4. On the Weyl matrix balls associated with matricial Caratheodory sequences......Page 313
5. On the Weyl matrix balls associated with reciprocal matrix-valued Caratheodory sequences......Page 319
6. Further observations on the matrix-valued functions Θn and Θn......Page 324
7. Some remarks on central q × q Carath´eodory functions......Page 331
References......Page 340
0. Introduction......Page 343
1. Extremal interpolation problems......Page 344
2. On a nonlinear matrix equation......Page 346
3. Methods of computation......Page 348
4. Schur extremal problem......Page 350
5. Nevanlinna-Pick extremal problem......Page 352
6. Jordan block diagonal structure......Page 354
References......Page 356
1. Introduction......Page 357
2. Preliminaries......Page 358
3. Structure for inverses of banded plus semiseparable matrices......Page 360
4. Fast solution of Ax = c......Page 362
5.1. A is a sum of diagonal and semiseparable matrix......Page 363
5.2. A is a sum of banded and semiseparable matrix......Page 364
Appendix......Page 365
References......Page 367
1. Introduction......Page 369
2.1. Integers......Page 370
2.3. General matrices......Page 371
2.4. Matrices with displacement structure: general properties......Page 372
2.5. Most popular matrices with displacement structure......Page 373
2.6. Randomization......Page 376
3.1. Inversion of strongly nonsingular structured matrices......Page 377
3.2. Inversion of nonsingular structured matrices in Zp......Page 379
3.3. The case of singular matrices with displacement structure......Page 380
5. Related works......Page 382
References......Page 383
1. Introduction......Page 387
2. Two-grid and multi-grid methods......Page 389
3. Two-grid and multi-grid methods for DCT-III matrices......Page 392
4. V-cycle optimal convergence......Page 395
5.1. Case x0 = 0 (differential-like problems)......Page 401
6. Computational costs and conclusions......Page 402
References......Page 405
1. Notation and problem formulation......Page 407
2. Main results......Page 409
3. Approximation of μn......Page 414
4. Appendix......Page 416
References......Page 428
1. Introduction......Page 431
2. Monotone iteration for finding positive eigenvector......Page 433
3. The numerical implementation in two-dimensional case......Page 436
References......Page 440
1. Introduction......Page 441
2. Series and matrices......Page 442
3. Jumps over zero minors......Page 443
5. Table of minors......Page 446
6. Pade theory......Page 448
References......Page 449