Matrix Methods: Theory, Algorithms and Applications

Contents......Page 10
Preface......Page 8
Algebra and Matrices......Page 16
1 Introduction......Page 17
2 Preliminaries......Page 20
3 Matrices over the binary Boolean semiring......Page 22
4 Matrices over antinegative semirings without zero divisors......Page 32
References......Page 33
1 Introduction......Page 35
2.1 Schur decompositions......Page 38
2.2 The polar decomposition......Page 40
2.3 The singular value decomposition (SVD)......Page 41
2.5 The QR decomposition......Page 42
2.6 The lU decomposition......Page 43
References......Page 44
Sensitivity Analysis of Hamiltonian and Reversible Systems Prone to Dissipation-Induced Instabilities O. N. Kirillov (Moscow State University)......Page 46
1 Introduction......Page 47
2.1 Stability of a circulatory system......Page 50
2.2 The influence of small damping and gyroscopic forces on the stability of a circulatory system......Page 53
3.1 Stability of a gyroscopic system......Page 62
3.2 The influence of small damping and non-conservative positional forces on the stability of a gyroscopic system......Page 63
4 The modified Maxwell-Bloch equations with mechanical applications......Page 69
4.1 Stability of Hauger's gyropendulum......Page 70
4.2 Friction-induced instabilities in rotating elastic bodies of revolution......Page 71
4.2.1 Deformation of the spectral mesh......Page 72
Conclusions......Page 78
References......Page 79
1 Introduction......Page 84
2 Miniversal deformations of matrices......Page 85
3 Miniversal deformations of matrix pencils......Page 91
4 Miniversal deformations of contragredient matrix pencils......Page 94
References......Page 99
1 Introduction......Page 100
2 The Schein rank of Boolean matrices......Page 101
3 Matrices of Schein rank 2, 3......Page 103
4 On coding of bipartite graphs by sets......Page 105
5 On canonical bipartite graphs......Page 106
6 On the Schein rank of Boolean matrices and the intersection number of associated graphs......Page 108
7 On coding of bipartite graphs by antichains......Page 110
8 Bipartite intersection graphs  k,p,q......Page 113
9 The Schein rank of  nxn......Page 116
References......Page 118
1 Introduction......Page 119
2.1 Lattice matrices and column vectors......Page 120
2.2 Brouwerian lattices......Page 121
2.4 Systems of linear equations over Brouwerian lattices......Page 122
3 Semilattices and lattices of matrix columns and matrix rows......Page 123
4 Subspaces of A-invariant column eigenvectors......Page 125
5 Lattices of invariant column vectors......Page 128
References......Page 129
1 Main definitions and notation......Page 131
2 Introduction......Page 132
3 On the lengths of algebra and its subalgebras......Page 134
3.1 Two block subalgebras in upper triangular matrix algebra......Page 137
3.2 Three block subalgebras in upper triangular matrix algebra......Page 146
3.3 Examples......Page 153
References......Page 154
1 Introduction......Page 155
2 Preparations......Page 158
3 Preliminaries......Page 161
4 Triangular factorization......Page 165
5 Eigenvectors of the matrix B......Page 169
References......Page 180
Reduction of a Set of Matrices over a Principal Ideal Domain to the Smith Normal Forms by Means of the Same One-Sided Transformations. V. M. Prokip (Pidstryhach Institute for Applied Problems of Mechanics and Mathematics)......Page 181
Acknowledgments......Page 188
References......Page 189
Matrices and Algorithms......Page 190
1 Introduction......Page 191
1.2 Application to transport equation......Page 193
2 Theoretical properties......Page 194
2.1 Some useful facts about nonnegative matrices......Page 195
2.3 Existence of nonnegative solutions......Page 196
2.4 The eigenvalue problem associated with the matrix equation......Page 197
2.5 The eigenvalues of H......Page 198
2.6 The differential of the Riccati operator......Page 200
2.7 The number of positive solutions......Page 201
3 Numerical methods......Page 203
3.1 Schur method......Page 204
3.2 Functional iterations......Page 205
3.3 Newton's method......Page 206
3.4 Doubling algorithms......Page 207
4.1 The shift technique......Page 212
4.2 Choosing a new initial value......Page 216
5 Numerical experiments and comparisons......Page 219
References......Page 221
1 Introduction......Page 225
2 Basic algorithm......Page 226
3 Final algorithm......Page 227
4 Numerical experiments......Page 229
5 Conclusions......Page 234
References......Page 235
There Exist Normal Hankel (   )-Circulants of Any Order n V. N. Chugunov (INM RAS), Kh. D. Ikramov (Moscow State University)......Page 237
References......Page 241
1 Introduction......Page 242
2 Reflection for image extension and BCs......Page 244
3 Image extension by anti-reflection......Page 248
4 Numerical experiments......Page 249
Acknowledgment......Page 251
References......Page 252
1 Introduction......Page 253
3 Evaluating the characteristic polynomial......Page 254
5 Example......Page 257
6 Generalization to  -matrices......Page 258
7 Conclusion......Page 260
References......Page 261
1 Introduction......Page 262
1.2 Definitions and basic lemmas......Page 263
2 Algorithm maxvol......Page 265
3.1 Theoretical estimates......Page 267
3.3 Maximization of bivariate functions......Page 269
4 Conclusion and future work......Page 270
References......Page 271
1 Introduction......Page 272
2 Multiplicative projector methods......Page 274
3 Additive projective methods......Page 277
4 Iterations in Krylov subspaces with dynamic preconditioning......Page 278
References......Page 279
1 Introduction......Page 281
2 Relationships between cu and tu......Page 283
References......Page 286
1 Introduction......Page 288
2 Problem setting......Page 289
3 Scaling techniques......Page 290
4 How to estimate GMRES convergence......Page 291
5.1 Main result......Page 293
5.2 The corresponding GMRES iteration number bound......Page 297
5.3 Relating the new estimate to scaling......Page 298
5.4 Relating the new estimate to ILU preconditioning......Page 300
6 Numerical experiments......Page 305
References......Page 309
1 Introduction......Page 311
2 Univariate case......Page 313
2.1 Moving lines and Toeplitz matrices......Page 314
2.2 Euclidean division......Page 316
2.3 Construction of the generators......Page 318
3.1 Moving hyperplanes......Page 322
3.2 Generators and reduction......Page 325
3.3 Interpolation......Page 326
References......Page 327
1 Introduction......Page 328
2 Basic principles of electronic structure calculations......Page 330
2.1 Density matrix formulation of Hartree-Fock and OFT models......Page 333
3 Hyperbolic cross approximation in wavelet bases......Page 334
4 Toolkit for tensor-product approximations......Page 338
4.1 Tensor-product representations in higher dimension......Page 339
4.2.1 Sine interpolation methods......Page 340
4.2.2 Integral representation methods......Page 342
4.2.3 On the best approximation by exponential sums......Page 343
5.1 Hierarchical matrix techniques......Page 346
5.2 Hierarchical Kronecker tensor-product approximations......Page 347
6 Linear scaling methods for Hartree-Fock and Kohn-Sham equations......Page 348
6.1 Matrix-valued functions approach for density matrices......Page 349
6.2 Computation of Hartree potentials in tensor-product formats......Page 350
7 Conclusions......Page 352
References......Page 353
Separation of Variables in Nonlinear Fermi Equation Yu. I. Kuznetsov (Novosibirsk Institute of Comp. Math. and Math. Geophysics)......Page 363
References......Page 368
Faster Multipoint Polynomial Evaluation via Structured Matrices B. Murphy (Lehman College), R . E. Rosholt (Lehman College)......Page 369
References......Page 371
1 Introduction......Page 372
2 A hard input class for GEPP......Page 373
3 Experimental results......Page 374
References......Page 377
1 Introduction......Page 379
2 Basic definitions......Page 380
3 Newton's iteration for matrix inversion. Its initialization and acceleration......Page 381
4 Structured iteration, recursive compressions, and autocorrection......Page 383
5 Homotopic (continuation) approach......Page 386
6 Splitting GSVDs......Page 389
7 Divide-and-conquer algorithms and computing singular subspaces......Page 391
8 Computation of null matrix bases......Page 392
9 Discussion......Page 393
References......Page 394
1 Introduction......Page 397
2.1 Reflective boundary conditions......Page 400
2.2 Anti-reflective boundary conditions......Page 402
3.1 Truncated SVDs and truncated SDs......Page 406
3.2 Tikhonov and re-blurring regularizations......Page 407
4 Cross-channel blurring......Page 409
5.1 Some computational issues......Page 410
5.2 Truncated decompositions......Page 411
5.2.1 Gray-scale images......Page 412
5.2.2 Color images in the case of cross-channel blurring......Page 417
5.3 Tikhonov and re-blurring regularizations......Page 418
References......Page 421
1 Introduction......Page 424
2 Polynomial matrices......Page 425
3 A difference equation......Page 428
References......Page 429
Matrices and Applications......Page 430
1 Statement of the problem......Page 431
2 The iterative process......Page 434
3 The investigation of the convergence of the iterative process......Page 438
4 Application of the iterative method to the problems (1)-(3)......Page 445
References......Page 447
1 Introduction......Page 448
2 The problem statement......Page 449
3 Multilevel k-way graphs partitioning......Page 450
4 Coarsening phase......Page 451
5 Initial partitioning phase......Page 455
6 Uncoarsening with refinement phase......Page 456
7 Cell-based multilevel approach......Page 457
8 Numerical test results......Page 458
9 Conclusion......Page 462
References......Page 463
1 Introduction......Page 464
General definitions......Page 465
2.1 Basic algorithm......Page 467
2.2 Algorithm: Kronecker products......Page 469
2.3.2 Extreme window sizes.......Page 471
2.3.3 Product of 1D sequences.......Page 472
2.4 Comments on grouping step......Page 473
3.1 Basic definitions......Page 474
3.2 Separability of 1D sequences......Page 475
3.3 Products of 10 sequences......Page 477
3.4 Checking the separability: Weighted correlations......Page 478
4.1 Basic properties......Page 479
4.2 Ranks of time series......Page 481
4.3.2 Polynomials.......Page 482
4.3.3 Sine-wave 2D-arrays.......Page 484
5 Example of analysis......Page 485
References......Page 488
1 Introduction......Page 489
2 General Ray Principle......Page 490
3 Formulation and theoretical justification of p-version of GR-method......Page 491
References......Page 494
1 Introduction......Page 497
2 Description of the algorithm......Page 498
3 Theoretical stability analysis......Page 500
4 Solution error......Page 502
5 Results of numerical experiments......Page 508
References......Page 513
Introduction......Page 515
1 Nonlinear finite volume method......Page 516
2 Monotonicity of the method......Page 521
References......Page 524
1 Introduction......Page 525
2.2 London equations for conductors of finite thickness......Page 527
2.3 Stream function......Page 529
3.1 Formulation......Page 530
3.2 Implementation......Page 531
3.3 Sparsification procedure......Page 532
4.2 Flux flow osciilator......Page 533
References......Page 536
1 Introduction......Page 538
2 Problem formulation......Page 539
3 Analysis of the equation......Page 541
4 Numerical solving of equation......Page 544
References......Page 547
1 Introduction......Page 548
3 Proposed techniques......Page 549
3.1 Block diagonalization......Page 550
3.2 Reduction......Page 551
4 Experimental results......Page 552
References......Page 553
1 Introduction......Page 554
2 Model problem......Page 555
3 Smoothing procedure in multigrid method......Page 556
4 Numerical results......Page 557
References......Page 558
2 Main equations......Page 561
3.1 Interpolation schemes for the spaces  and  ......Page 565
3.2 Matrix A construction......Page 567
References......Page 570
1 Introduction......Page 572
2 Mathematical statement of the polarized radiation transfer problem......Page 573
3 The influence function of the vector boundary-value problem of the transfer theory......Page 576
4 The vector transfer operator......Page 579
5 The mathematical model of polarized radiation transfer in two-media system......Page 581
6 The vector influence functions for two-media system......Page 584
7 Matrix transfer operator for two-media system......Page 586
8 Mathematical model of polarized radiation transfer In multi-media heterogeneous system......Page 588
References......Page 593
1 Formulation of the problem......Page 594
2 Method of augmented systems......Page 595
3 Numerical examples......Page 598
References......Page 600
Author Index......Page 602