Bini / Mehrmann / Olshevsky Numerical Methods for Structured Matrices and Applications

The Georg Heinig Memorial Volume
1. Auflage 2011
ISBN: 978-3-7643-8996-3
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 199, 439 Seiten

Reihe: Operator Theory: Advances and Applications

This cross-disciplinary volume brings together theoretical mathematicians, engineers and numerical analysts and publishes surveys and research articles related to topics such as fast algorithms, in which the late Georg Heinig made outstanding achievements.

Autoren/Hrsg.

Mehrmann, Volker

Olshevsky, Vadim

Tyrtsyhnikov, Eugene

Bini, Dario Andrea

Barel, Marc Van

Inhaltsverzeichnis

1;Title Page;3
2;Copyright Page;4
3;Table of Contents;5
4;Foreword;7
5;Part I Georg Heinig;9
6;Georg Heinig (1947–2005) In Memoriam;10
7;Georg Heinig November 24, 1947 – May 10, 2005 A Personal Memoir and Appreciation;14
7.1;References;19
7.2;List of Georg Heinig’s (refereed) publications;19
8;Introduction to Bezoutians;31
8.1;Foreword;31
8.2;1. Preliminaries;36
8.2.1;1. Notation.;36
8.2.2;2. Sylvester’s inertia law.;37
8.2.3;3. Toeplitz, Hankel, and Toeplitz-plus-Hankel matrices.;37
8.2.4;4. Quasi-Toeplitz matrices, quasi-Hankel matrices, and quasi-T+H matrices.;38
8.2.5;5. Mobius transformations.;39
8.3;2. Definitions and properties for the Hankel and Toeplitz case;41
8.3.1;1. Hankel Bezoutians.;41
8.3.2;2. The transformation .H.;44
8.3.3;3. Uniqueness.;44
8.3.4;4. Quasi-H-Bezoutians.;45
8.3.5;5. Frobenius-Fischer transformations.;46
8.3.6;6. Splitting of H-Bezoutians.;46
8.3.7;7. Toeplitz Bezoutians.;47
8.3.8;8. The transformation .T .;49
8.3.9;9. Symmetric and skewsymmetric T-Bezoutians.;49
8.3.10;10. Hermitian T-Bezoutians.;50
8.3.11;11. Splitting of symmetric T-Bezoutians.;51
8.3.12;12. Relations between H- and T-Bezoutians.;53
8.4;3. Resultant matrices and matrix representations of Bezoutians;54
8.4.1;1. Kravitsky-Russakovsky formulas.;54
8.4.2;2. Matrix representations of Bezoutians.;55
8.4.3;3. Bezoutians as Schur complements.;56
8.5;4. Inverses of Hankel and Toeplitz matrices;57
8.5.1;1. Inverses of Hankel matrices.;57
8.5.2;2. Characterization of fundamental systems.;59
8.5.3;3. Christoffel-Darboux formula.;59
8.5.4;4. Inverses of Toeplitz matrices.;59
8.5.5;5. Characterization of fundamental systems.;60
8.5.6;6. Inverses of symmetric Toeplitz matrices.;62
8.5.7;7. Inverses of skewsymmetric Toeplitz matrices.;63
8.5.8;8. Inverses of Hermitian Toeplitz matrices.;64
8.5.9;9. Solution of systems.;65
8.6;5. Generalized triangular factorizations of Bezoutians;65
8.6.1;1. Division with remainder.;65
8.6.2;2. Factorization step for H-Bezoutians.;65
8.6.3;3. Euclidian algorithm.;66
8.6.4;4. Generalized UL-factorization of H-Bezoutians.;66
8.6.5;5. Inertia computation.;67
8.6.6;6. Factorization step for T-Bezoutians in the generic case.;67
8.6.7;7. LU-factorization of T-Bezoutians.;68
8.6.8;8. Non-generic case for T-Bezoutians.;69
8.6.9;9. Hermitian T-Bezoutians.;70
8.7;6. Bezoutians and companion matrices;71
8.7.1;1. Factorization of the companion.;71
8.7.2;2. Functional calculus.;72
8.7.3;3. Barnett’s formula.;73
8.7.4;4. Barnett’s formula for T-Bezoutians.;73
8.8;7. Hankel matrices generated by rational functions;74
8.8.1;1. Generating functions of Hankel matrices.;74
8.8.2;2. Vandermonde factorization of Hankel matrices.;77
8.8.3;3.Real Hankel matrices.;78
8.8.4;4. The Cauchy index.;79
8.8.5;5. Congruence to H-Bezoutians.;80
8.8.6;6. Inverses of H-Bezoutians.;82
8.8.7;7. Solving the Bezout equation.;82
8.9;8. Toeplitz matrices generated by rational functions;83
8.9.1;1. Generating functions of Toeplitz matrices.;83
8.9.2;2. Matrices with symmetry properties.;85
8.9.3;3. Vandermonde factorization of nonsingular Toeplitz matrices.;86
8.9.4;4. Hermitian Toeplitz matrices.;87
8.9.5;5. Signature and Cauchy index.;87
8.9.6;6. Congruence to T-Bezoutians.;88
8.9.7;7. Inverses of T-Bezoutians.;89
8.9.8;8. Relations between Toeplitz and Hankel matrices.;90
8.10;9. Vandermonde reduction of Bezoutians;90
8.10.1;1. Non-confluent Hankel case.;91
8.10.2;2. Non-confluent Toeplitz case.;92
8.10.3;3. Confluent case.;93
8.11;10. Root localization problems;95
8.11.1;1. Inertia of polynomials.;95
8.11.2;2. Inertia with respect to the real line.;95
8.11.3;3. Real roots of real polynomials.;97
8.11.4;4. Inertia with respect to the imaginary axis.;98
8.11.5;5. Roots on the imaginary axis and positive real roots of real polynomials.;99
8.11.6;6. Inertia with respect to the unit circle.;100
8.11.7;7. Roots of conjugate-symmetric polynomials.;101
8.12;11. Toeplitz-plus-Hankel Bezoutians;101
8.12.1;1. Definition.;101
8.12.2;2. The transformation .T+H.;102
8.12.3;3. Uniqueness.;102
8.12.4;4. Inverses of T+H-Bezoutians.;104
8.13;12. Inverses of T+H-matrices;105
8.13.1;1. Fundamental systems.;105
8.13.2;2. Inversion of T+H matrices.;106
8.13.3;3. Inversion of symmetric T+H matrices.;109
8.13.4;4. Inversion of centrosymmetric T+H matrices.;110
8.13.5;5. Inversion of centro-skewsymmetric T+H matrices.;112
8.14;13. Exercises;116
8.15;14. Notes;119
8.16;References;120
9;On Matrices that are not Similar to a Toeplitz Matrix and a Family of Polynomials;125
9.1;1. Introduction;125
9.2;2. On a family of polynomials;127
9.3;3. Appendix;128
9.4;References;129
10;Part II Research Contributions;130
11;A Traub-like Algorithm for Hessenberg quasiseparable-Vandermonde Matrices of Arbitrary Order;131
11.1;1. Introduction. Polynomial-Vandermonde matrices and quasiseparable matrices;132
11.1.1;1.1. Inversion of polynomial-Vandermonde matrices;132
11.1.2;1.2. Capturing recurrence relations via confederate matrices;132
11.1.3;1.3. Main tool: quasiseparable matrices and polynomials;135
11.1.4;1.4. Main problem: Inversion of (H,m)-quasiseparable-Vandermonde matrices;136
11.2;2. Inversion formula;137
11.2.1;2.1. The key property of all Traub-like algorithms: pertransposition;138
11.3;3. Recurrence relations for (H,m)-quasiseparable polynomials;140
11.3.1;3.1. Generators of quasiseparable matrices;141
11.3.2;3.2. Sparse recurrence relations for (H,m)-quasiseparable polynomials;142
11.4;4. Recurrence relations for polynomials associated with (H,m)-quasiseparable polynomials;144
11.4.1;4.1. Introduction of a perturbation term via pertransposition of confederate matrices;144
11.4.2;4.2. Perturbed [EGO05]-type recurrence relations;145
11.4.3;4.3. Known special cases of these more general recurrence relations;147
11.5;5. Computing the coefficients of the master polynomial;149
11.6;6. The overall Traub-like algorithm;151
11.6.1;6.1. Quasiseparable generator input;151
11.6.2;6.2. Recurrence relation coefficient input;152
11.7;7. Numerical Experiments;153
11.8;8. Conclusions;154
11.9;References;156
12;A Fast Algorithm for Approximate Polynomial GCD Based on Structured Matrix Computations;159
12.1;1. Introduction;159
12.2;2. Resultant matrices and -gcd;162
12.2.1;2.1. Sylvester and B´ezout matrices;162
12.2.2;2.2. Cauchy-like matrices;163
12.2.3;2.3. Modified GKO algorithm;165
12.3;3. Fast -gcd computation;166
12.3.1;3.1. Estimating degree and coefficients of the -gcd;166
12.3.2;3.2. Refinement;167
12.3.3;3.3. The overall algorithm;170
12.4;4. Numerical experiments;171
12.4.1;4.1. Badly conditioned polynomials;172
12.4.2;4.2. High gcd degree;173
12.4.3;4.3. Unbalanced coefficients;174
12.4.4;4.4. Multiple roots;174
12.4.5;4.5. Small leading coefficient;174
12.4.6;4.6. Running time;175
12.5;References;176
13;On Inertia of Some Structured Hermitian Matrices;178
13.1;1. Introduction;178
13.2;2. The interior case;181
13.3;3. The boundary case;185
13.4;References;192
14;Variable-coefficient Toeplitz Matrices with Symbols beyond the Wiener Algebra;193
14.1;1. Introduction;193
14.2;2. H¨older continuity;196
14.3;3. Counterexamples;197
14.4;4. Sufficient conditions;199
14.5;5. Discontinuous generating functions;203
14.6;References;203
15;A Priori Estimates on the Structured Conditioning of Cauchy and Vandermonde Matrices;205
15.1;1. Introduction;205
15.1.1;1.1. Main definitions and notations;207
15.1.2;1.2. Basic displacement structured matrices;208
15.2;2. Cauchy matrices;209
15.3;3. Vandermonde matrices;210
15.3.1;3.1. Vandermonde matrices with nonnegative nodes;214
15.3.2;3.2. Vandermonde matrices with symmetric nodes;215
15.4;4. Cauchy-Vandermonde matrices;217
15.5;References;220
16;Factorizations of Totally Negative Matrices;223
16.1;1. Introduction and background;223
16.2;2. Auxiliary results;225
16.3;3. QR decomposition of TN matrices;226
16.4;4. Symmetric-triangular decomposition of TN matrices;227
16.5;References;229
17;QR-factorization of Displacement Structured Matrices Using a Rank Structured Matrix Approach;230
17.1;1. Introduction;230
17.2;2. Rank Structure Preliminaries;232
17.3;3. QR-factorization of displacement structured matrices;234
17.4;4. The Cauchy-like case;239
17.5;5. The Vandermonde-like case;248
17.6;6. The Toeplitz-like case;249
17.7;7. Numerical experiments;251
17.8;References;254
18;Bezoutians Applied to Least Squares Approximation of Rational Functions;256
18.1;1. Introduction;256
18.2;2. The construction of h.;260
18.3;3. Bezoutians;262
18.4;4. The matrix L for . = 1 and indefinite G;263
18.5;5. The unit circle case . = T;266
18.6;6. The imaginary axis case . = iR;269
18.7;7. Computation of h. via its minimal realizations;273
18.8;8. The construction of h.;274
18.9;9. The limit behavior of Q;276
18.10;10. Bilinear transformation between D and H ;279
18.11;11. Examples;280
18.12;References;287
19;On the Weyl Matrix Balls Corresponding to the Matricial Caratheodory Problem in Both Nondegenerate and Degenerate Cases;290
19.1;0. Introduction;290
19.2;1. Preliminaries;292
19.3;2. On a parametrization of the solution set Cq[D, (Gj)nj=0];295
19.4;3. Particular matrix-valued Schur functions associated with given q × q Carath´eodory sequences;298
19.5;4. On the Weyl matrix balls associated with matricial Caratheodory sequences;304
19.6;5. On the Weyl matrix balls associated with reciprocal matrix-valued Caratheodory sequences;310
19.7;6. Further observations on the matrix-valued functions Tn and Tn;315
19.8;7. Some remarks on central q × q Carath´eodory functions;322
19.9;References;331
20;On Extremal Problems of Interpolation Theory with Unique Solution;334
20.1;0. Introduction;334
20.2;1. Extremal interpolation problems;335
20.3;2. On a nonlinear matrix equation;337
20.4;3. Methods of computation;339
20.5;4. Schur extremal problem;341
20.6;5. Nevanlinna-Pick extremal problem;343
20.7;6. Jordan block diagonal structure;345
20.8;References;347
21;O(n) Algorithms for Banded Plus Semiseparable Matrices;348
21.1;1. Introduction;348
21.2;2. Preliminaries;349
21.3;3. Structure for inverses of banded plus semiseparable matrices;351
21.4;4. Fast solution of Ax = c;353
21.5;5. Numerical results;354
21.5.1;5.1. A is a sum of diagonal and semiseparable matrix;354
21.5.2;5.2. A is a sum of banded and semiseparable matrix;355
21.6;6. Conclusions;356
21.7;Appendix;356
21.8;References;358
22;Unified Nearly Optimal Algorithms for Structured Integer Matrices;360
22.1;1. Introduction;360
22.2;2. Definitions and basic facts;361
22.2.1;2.1. Integers;361
22.2.2;2.2. Polynomial and integer multiplication;362
22.2.3;2.3. General matrices;362
22.2.4;2.4. Matrices with displacement structure: general properties;363
22.2.5;2.5. Most popular matrices with displacement structure;364
22.2.6;2.6. Randomization;367
22.3;3. Computations in Zp with matrices having displacement structure;368
22.3.1;3.1. Inversion of strongly nonsingular structured matrices;368
22.3.2;3.2. Inversion of nonsingular structured matrices in Zp;370
22.3.3;3.3. The case of singular matrices with displacement structure;371
22.4;4. Computations with structured integer matrices;373
22.5;5. Related works;373
22.6;References;374
23;V-cycle Optimal Convergence for DCT-III Matrices;377
23.1;1. Introduction;377
23.2;2. Two-grid and multi-grid methods;379
23.3;3. Two-grid and multi-grid methods for DCT-III matrices;382
23.4;4. V-cycle optimal convergence;385
23.5;5. Numerical experiments;391
23.5.1;5.1. Case x0 = 0 (differential-like problems);391
23.5.2;5.2. Case x0 = p (integral-like problems);392
23.6;6. Computational costs and conclusions;392
23.7;References;395
24;The Ratio Between the Toeplitz and the Unstructured Condition Number;397
24.1;1. Notation and problem formulation;397
24.2;2. Main results;399
24.3;3. Approximation of µn;404
24.4;4. Appendix;406
24.5;References;418
25;A New Algorithm for Finding Positive Eigenvectors for a Class of Nonlinear Operators Associated with M-matrices;420
25.1;1. Introduction;420
25.2;2. Monotone iteration for finding positive eigenvector;422
25.3;3. The numerical implementation in two-dimensional case;425
25.4;References;429
26;Hankel Minors and Pade Approximations;430
26.1;1. Introduction;430
26.2;2. Series and matrices;431
26.3;3. Jumps over zero minors;432
26.4;4. An identity for determinants;435
26.5;5. Table of minors;435
26.6;6. Pade theory;437
26.7;References;438