Numerical Methods for Structured Matrices and Applications (eBook)

Title Page 3
Copyright Page 4
Table of Contents 5
Foreword 7
Part I Georg Heinig 9
Georg Heinig (1947–2005) In Memoriam 10
Georg Heinig November 24, 1947 – May 10, 2005 A Personal Memoir and Appreciation 14
References 19
List of Georg Heinig’s (refereed) publications 19
Introduction to Bezoutians 31
Foreword 31
1. Preliminaries 36
1. Notation. 36
2. Sylvester’s inertia law. 37
3. Toeplitz, Hankel, and Toeplitz-plus-Hankel matrices. 37
4. Quasi-Toeplitz matrices, quasi-Hankel matrices, and quasi-T+H matrices. 38
5. Mobius transformations. 39
2. Definitions and properties for the Hankel and Toeplitz case 41
1. Hankel Bezoutians. 41
2. The transformation .H. 44
3. Uniqueness. 44
4. Quasi-H-Bezoutians. 45
5. Frobenius-Fischer transformations. 46
6. Splitting of H-Bezoutians. 46
7. Toeplitz Bezoutians. 47
8. The transformation .T . 49
9. Symmetric and skewsymmetric T-Bezoutians. 49
10. Hermitian T-Bezoutians. 50
11. Splitting of symmetric T-Bezoutians. 51
12. Relations between H- and T-Bezoutians. 53
3. Resultant matrices and matrix representations of Bezoutians 54
1. Kravitsky-Russakovsky formulas. 54
2. Matrix representations of Bezoutians. 55
3. Bezoutians as Schur complements. 56
4. Inverses of Hankel and Toeplitz matrices 57
1. Inverses of Hankel matrices. 57
2. Characterization of fundamental systems. 59
3. Christoffel-Darboux formula. 59
4. Inverses of Toeplitz matrices. 59
5. Characterization of fundamental systems. 60
6. Inverses of symmetric Toeplitz matrices. 62
7. Inverses of skewsymmetric Toeplitz matrices. 63
8. Inverses of Hermitian Toeplitz matrices. 64
9. Solution of systems. 65
5. Generalized triangular factorizations of Bezoutians 65
1. Division with remainder. 65
2. Factorization step for H-Bezoutians. 65
3. Euclidian algorithm. 66
4. Generalized UL-factorization of H-Bezoutians. 66
5. Inertia computation. 67
6. Factorization step for T-Bezoutians in the generic case. 67
7. LU-factorization of T-Bezoutians. 68
8. Non-generic case for T-Bezoutians. 69
9. Hermitian T-Bezoutians. 70
6. Bezoutians and companion matrices 71
1. Factorization of the companion. 71
2. Functional calculus. 72
3. Barnett’s formula. 73
4. Barnett’s formula for T-Bezoutians. 73
7. Hankel matrices generated by rational functions 74
1. Generating functions of Hankel matrices. 74
2. Vandermonde factorization of Hankel matrices. 77
3.Real Hankel matrices. 78
4. The Cauchy index. 79
5. Congruence to H-Bezoutians. 80
6. Inverses of H-Bezoutians. 82
7. Solving the Bezout equation. 82
8. Toeplitz matrices generated by rational functions 83
1. Generating functions of Toeplitz matrices. 83
2. Matrices with symmetry properties. 85
3. Vandermonde factorization of nonsingular Toeplitz matrices. 86
4. Hermitian Toeplitz matrices. 87
5. Signature and Cauchy index. 87
6. Congruence to T-Bezoutians. 88
7. Inverses of T-Bezoutians. 89
8. Relations between Toeplitz and Hankel matrices. 90
9. Vandermonde reduction of Bezoutians 90
1. Non-confluent Hankel case. 91
2. Non-confluent Toeplitz case. 92
3. Confluent case. 93
10. Root localization problems 95
1. Inertia of polynomials. 95
2. Inertia with respect to the real line. 95
3. Real roots of real polynomials. 97
4. Inertia with respect to the imaginary axis. 98
5. Roots on the imaginary axis and positive real roots of real polynomials. 99
6. Inertia with respect to the unit circle. 100
7. Roots of conjugate-symmetric polynomials. 101
11. Toeplitz-plus-Hankel Bezoutians 101
1. Definition. 101
2. The transformation .T+H. 102
3. Uniqueness. 102
4. Inverses of T+H-Bezoutians. 104
12. Inverses of T+H-matrices 105
1. Fundamental systems. 105
2. Inversion of T+H matrices. 106
3. Inversion of symmetric T+H matrices. 109
4. Inversion of centrosymmetric T+H matrices. 110
5. Inversion of centro-skewsymmetric T+H matrices. 112
13. Exercises 116
14. Notes 119
References 120
On Matrices that are not Similar to a Toeplitz Matrix and a Family of Polynomials 125
1. Introduction 125
2. On a family of polynomials 127
3. Appendix 128
References 129
Part II Research Contributions 130
A Traub-like Algorithm for Hessenberg quasiseparable-Vandermonde Matrices of Arbitrary Order 131
1. Introduction. Polynomial-Vandermonde matrices and quasiseparable matrices 132
1.1. Inversion of polynomial-Vandermonde matrices 132
1.2. Capturing recurrence relations via confederate matrices 132
1.3. Main tool: quasiseparable matrices and polynomials 135
1.4. Main problem: Inversion of (H,m)-quasiseparable-Vandermonde matrices 136
2. Inversion formula 137
2.1. The key property of all Traub-like algorithms: pertransposition 138
3. Recurrence relations for (H,m)-quasiseparable polynomials 140
3.1. Generators of quasiseparable matrices 141
3.2. Sparse recurrence relations for (H,m)-quasiseparable polynomials 142
4. Recurrence relations for polynomials associated with (H,m)-quasiseparable polynomials 144
4.1. Introduction of a perturbation term via pertransposition of confederate matrices 144
4.2. Perturbed [EGO05]-type recurrence relations 145
4.3. Known special cases of these more general recurrence relations 147
5. Computing the coefficients of the master polynomial 149
6. The overall Traub-like algorithm 151
6.1. Quasiseparable generator input 151
6.2. Recurrence relation coefficient input 152
7. Numerical Experiments 153
8. Conclusions 154
References 156
A Fast Algorithm for Approximate Polynomial GCD Based on Structured Matrix Computations 159
1. Introduction 159
2. Resultant matrices and -gcd 162
2.1. Sylvester and B´ezout matrices 162
2.2. Cauchy-like matrices 163
2.3. Modified GKO algorithm 165
3. Fast -gcd computation 166
3.1. Estimating degree and coefficients of the -gcd 166
3.2. Refinement 167
3.3. The overall algorithm 170
4. Numerical experiments 171
4.1. Badly conditioned polynomials 172
4.2. High gcd degree 173
4.3. Unbalanced coefficients 174
4.4. Multiple roots 174
4.5. Small leading coefficient 174
4.6. Running time 175
References 176
On Inertia of Some Structured Hermitian Matrices 178
1. Introduction 178
2. The interior case 181
3. The boundary case 185
References 192
Variable-coefficient Toeplitz Matrices with Symbols beyond the Wiener Algebra 193
1. Introduction 193
2. H¨older continuity 196
3. Counterexamples 197
4. Sufficient conditions 199
5. Discontinuous generating functions 203
References 203
A Priori Estimates on the Structured Conditioning of Cauchy and Vandermonde Matrices 205
1. Introduction 205
1.1. Main definitions and notations 207
1.2. Basic displacement structured matrices 208
2. Cauchy matrices 209
3. Vandermonde matrices 210
3.1. Vandermonde matrices with nonnegative nodes 214
3.2. Vandermonde matrices with symmetric nodes 215
4. Cauchy-Vandermonde matrices 217
References 220
Factorizations of Totally Negative Matrices 223
1. Introduction and background 223
2. Auxiliary results 225
3. QR decomposition of TN matrices 226
4. Symmetric-triangular decomposition of TN matrices 227
References 229
QR-factorization of Displacement Structured Matrices Using a Rank Structured Matrix Approach 230
1. Introduction 230
2. Rank Structure Preliminaries 232
3. QR-factorization of displacement structured matrices 234
4. The Cauchy-like case 239
5. The Vandermonde-like case 248
6. The Toeplitz-like case 249
7. Numerical experiments 251
References 254
Bezoutians Applied to Least Squares Approximation of Rational Functions 256
1. Introduction 256
2. The construction of h. 260
3. Bezoutians 262
4. The matrix L for . = 1 and indefinite G 263
5. The unit circle case . = T 266
6. The imaginary axis case . = iR 269
7. Computation of h. via its minimal realizations 273
8. The construction of h. 274
9. The limit behavior of Q 276
10. Bilinear transformation between D and H 279
11. Examples 280
References 287
On the Weyl Matrix Balls Corresponding to the Matricial Caratheodory Problem in Both Nondegenerate and Degenerate Cases 290
0. Introduction 290
1. Preliminaries 292
2. On a parametrization of the solution set Cq[D, (Gj)nj=0] 295
3. Particular matrix-valued Schur functions associated with given q × q Carath´eodory sequences 298
4. On the Weyl matrix balls associated with matricial Caratheodory sequences 304
5. On the Weyl matrix balls associated with reciprocal matrix-valued Caratheodory sequences 310
6. Further observations on the matrix-valued functions Tn and Tn 315
7. Some remarks on central q × q Carath´eodory functions 322
References 331
On Extremal Problems of Interpolation Theory with Unique Solution 334
0. Introduction 334
1. Extremal interpolation problems 335
2. On a nonlinear matrix equation 337
3. Methods of computation 339
4. Schur extremal problem 341
5. Nevanlinna-Pick extremal problem 343
6. Jordan block diagonal structure 345
References 347
O(n) Algorithms for Banded Plus Semiseparable Matrices 348
1. Introduction 348
2. Preliminaries 349
3. Structure for inverses of banded plus semiseparable matrices 351
4. Fast solution of Ax = c 353
5. Numerical results 354
5.1. A is a sum of diagonal and semiseparable matrix 354
5.2. A is a sum of banded and semiseparable matrix 355
6. Conclusions 356
Appendix 356
References 358
Unified Nearly Optimal Algorithms for Structured Integer Matrices 360
1. Introduction 360
2. Definitions and basic facts 361
2.1. Integers 361
2.2. Polynomial and integer multiplication 362
2.3. General matrices 362
2.4. Matrices with displacement structure: general properties 363
2.5. Most popular matrices with displacement structure 364
2.6. Randomization 367
3. Computations in Zp with matrices having displacement structure 368
3.1. Inversion of strongly nonsingular structured matrices 368
3.2. Inversion of nonsingular structured matrices in Zp 370
3.3. The case of singular matrices with displacement structure 371
4. Computations with structured integer matrices 373
5. Related works 373
References 374
V-cycle Optimal Convergence for DCT-III Matrices 377
1. Introduction 377
2. Two-grid and multi-grid methods 379
3. Two-grid and multi-grid methods for DCT-III matrices 382
4. V-cycle optimal convergence 385
5. Numerical experiments 391
5.1. Case x0 = 0 (differential-like problems) 391
5.2. Case x0 = p (integral-like problems) 392
6. Computational costs and conclusions 392
References 395
The Ratio Between the Toeplitz and the Unstructured Condition Number 397
1. Notation and problem formulation 397
2. Main results 399
3. Approximation of µn 404
4. Appendix 406
References 418
A New Algorithm for Finding Positive Eigenvectors for a Class of Nonlinear Operators Associated with M-matrices 420
1. Introduction 420
2. Monotone iteration for finding positive eigenvector 422
3. The numerical implementation in two-dimensional case 425
References 429
Hankel Minors and Pade Approximations 430
1. Introduction 430
2. Series and matrices 431
3. Jumps over zero minors 432
4. An identity for determinants 435
5. Table of minors 435
6. Pade theory 437
References 438