LEADER 12986nam 22006735 450 001 9910166058103321 005 20200705052228.0 010 $a3-319-49887-8 024 7 $a10.1007/978-3-319-49887-4 035 $a(CKB)3710000001080095 035 $a(DE-He213)978-3-319-49887-4 035 $a(MiAaPQ)EBC6298156 035 $a(MiAaPQ)EBC5610315 035 $a(Au-PeEL)EBL5610315 035 $a(OCoLC)1079006975 035 $a(PPN)198868413 035 $a(EXLCZ)993710000001080095 100 $a20170201d2016 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt$2rdacontent 182 $cc$2rdamedia 183 $acr$2rdacarrier 200 10$aExploiting Hidden Structure in Matrix Computations: Algorithms and Applications $eCetraro, Italy 2015 /$fby Michele Benzi, Dario Bini, Daniel Kressner, Hans Munthe-Kaas, Charles Van Loan ; edited by Michele Benzi, Valeria Simoncini 205 $a1st ed. 2016. 210 1$aCham :$cSpringer International Publishing :$cImprint: Springer,$d2016. 215 $a1 online resource (IX, 406 p. 57 illus., 46 illus. in color.) 225 1 $aC.I.M.E. Foundation Subseries ;$v2173 311 $a3-319-49886-X 327 $aIntro -- Preface -- Acknowledgments -- Contents -- Structured Matrix Problems from Tensors -- 1 Introduction -- 2 The Exploitation of Structure in Matrix Computations -- 2.1 Exploiting Data Sparsity -- 2.2 Exploiting Structured Eigensystems -- 2.3 Exploiting the Right Representation -- 2.4 Exploiting Orthogonality Structures -- 2.5 Exploiting a Structured Data layout -- 3 Matrix-Tensor Connections -- 3.1 Talking About Tensors -- 3.2 Tensor Parts: Fibers and Slices -- 3.3 Order-4 Tensors and Block Matrices -- 3.4 Modal Unfoldings -- 3.5 The vec Operation -- 3.6 The Kronecker Product -- 3.7 Perfect Shuffles, Kronecker Products, and Transposition -- 3.8 Tensor Notation -- 3.9 The Tensor Product -- 4 A Rank-1 Tensor Problem -- 4.1 Rank-1 Matrices -- 4.2 Rank-1 Tensors -- 4.3 The Nearest Rank-1 Problem for Matrices -- 4.4 A Nearest Rank-1 Tensor Problem -- 5 The Variational Approach to Tensor Singular Values -- 5.1 Rayleigh Quotient/Power Method Ideas: The Matrix Case -- 5.2 Rayleigh Quotient/Power Method Ideas: The Tensor Case -- 5.3 A First Look at Tensor Rank -- 6 Tensor Symmetry -- 6.1 Tensor Transposition -- 6.2 Symmetric Tensors -- 6.3 Symmetric Rank -- 6.4 The Eigenvalues of a Symmetric Tensor -- 6.5 Symmetric Embeddings -- 7 The Tucker Decomposition -- 7.1 Tucker Representations: The Matrix Case -- 7.2 Tucker Representations: The Tensor Case -- 7.3 The Mode-k Product -- 7.4 The Core Tensor -- 7.5 The Higher-Order SVD -- 7.6 The Tucker Nearness Problem -- 7.7 A Jacobi Approach -- 8 The CP Decomposition -- 8.1 CP Representations: The Matrix Case -- 8.2 CP Representation: The Tensor Case -- 8.3 More About Tensor Rank -- 8.4 The Nearest CP Problem -- 8.5 The Khatri-Rao Product -- 8.6 Equivalent Formulations -- 9 The Kronecker Product SVD -- 9.1 The Nearest Kronecker Product Problem -- 9.2 The Kronecker Product SVD (KPSVD). 327 $a9.3 Order-4 Tensor Approximation Using the KPSVD -- 10 The Tensor Train SVD -- 10.1 Tensor Trains and Data Sparsity -- 10.2 Computing an SVD-Based Tensor Train Representation -- 11 Tensor Problems with Multiple Symmetries -- 11.1 A First Look at Multiple Symmetries -- 11.2 A Tensor Problem with Multiple Symmetries -- 11.3 Perfect Shuffle Symmetry -- 11.4 Block Diagonalization -- 11.5 Low-Rank PS-Symmetric Approximation -- References -- Matrix Structures in Queuing Models -- 1 Introduction to Matrix Structures -- 1.1 Some Examples of Matrix Structures -- 2 Structures Encountered in Queuing Models -- 2.1 Markov Chains -- 2.2 Some Examples -- 2.3 Other Structures -- 3 Fundamentals on Structured Matrices -- 3.1 Classical Results on Toeplitz Matrices -- 3.2 Toeplitz Matrices, Polynomials and Power Series -- 3.3 Toeplitz Matrices, Trigonometric Algebras, and FFT -- 3.3.1 Circulant Matrices -- 3.3.2 z-Circulant Matrices -- 3.3.3 Matrix Embedding -- 3.3.4 Triangular Toeplitz Matrices -- 3.3.5 z-Circulant and Triangular Toeplitz Matrices -- 3.3.6 Other Matrix Algebras -- 3.4 Displacement Operators -- 3.4.1 Other Operators: Cauchy-Like Matrices -- 3.5 Algorithms for Toeplitz Inversion -- 3.5.1 Super-Fast Toeplitz Solvers -- 3.6 Asymptotic Spectral Properties and Preconditioning -- 3.6.1 Trigonometric Matrix Algebras and Preconditioning -- 3.7 Rank Structures -- 3.8 Bibliographical Notes -- 4 Algorithms for Structured Markov Chains: The Finite Case -- 4.1 The Block Tridiagonal Case -- 4.2 The Case of a Block Hessenberg Matrix -- 4.3 Applicability of CR -- 4.4 A Functional Interpretation of Cyclic Reduction -- 4.4.1 Convergence Properties When 1{?m,?m+1} -- 4.5 A Special Case: Non-skip-Free Markov Chain -- 4.6 A Special Case: QBD with Tridiagonal Blocks -- 5 Algorithms for Structured Markov Chains: The Infinite Case -- 5.1 M/G/1-Type Markov Chains. 327 $a5.2 G/M/1-Type Markov Chains -- 5.3 QBD Markov Chains -- 5.4 Computing Matrices G and R: The Weak Canonical Factorization -- 5.4.1 Solving Matrix Equations -- 5.4.2 Solving Matrix Equations by Means of CR: The QBD Case -- 5.4.3 Solving Matrix Equations by Means of CR: The M/G/1 and G/M/1 Cases -- 5.5 Shifting Techniques -- 5.5.1 Shift to the Right -- 5.6 Shift to the Left -- 5.7 Double Shift -- 5.8 Shifts and Canonical Factorizations -- 5.9 Available Software -- 6 Other Problems -- 6.1 Tree-Like Processes -- 6.2 Vector Equations -- 6.2.1 An Optimistic Approach -- 7 Exponential of a Block Triangular Block Toeplitz Matrix -- 7.1 Using ?-Circulant Matrices -- 7.2 Using Circulant Matrices -- 7.3 Method Based on Taylor Expansion -- References -- Matrices with Hierarchical Low-Rank Structures -- 1 Introduction -- 1.1 Sparsity Versus Data-Sparsity -- 1.2 Applications of Hierarchical Low-Rank Structures -- 1.3 Outline -- 2 Low-Rank Approximation -- 2.1 The SVD and Best Low-Rank Approximation -- 2.2 Stability of SVD and Low-Rank Approximation -- 2.3 Algorithms for Low-Rank Approximation -- 2.3.1 SVD-Based Algorithms -- 2.3.2 Lanczos-Based Algorithms -- 2.3.3 Randomized Algorithms -- 2.3.4 Adaptive Cross Approximation (ACA) -- 2.4 A Priori Approximation Results -- 2.4.1 Separability and Low Rank -- 2.4.2 Low Rank Approximation via Semi-separable Approximation -- 3 Partitioned Low-Rank Structures -- 3.1 HODLR Matrices -- 3.1.1 Matrix-Vector Multiplication -- 3.1.2 Matrix Addition -- 3.1.3 Matrix Multiplication -- 3.1.4 Matrix Factorization and Linear Systems -- 3.2 General Clustering Strategies -- 3.2.1 Geometrical Clustering -- 3.2.2 Algebraic Clustering -- 3.3 H-Matrices -- 3.4 Approximation of Elliptic Boundary Value Problems by H-Matrices -- 4 Partitioned Low-Rank Structures with Nested Low-Rank Representations -- 4.1 HSS Matrices -- 4.2 H2-Matrices. 327 $aReferences -- Localization in Matrix Computations: Theory and Applications -- 1 Introduction -- 1.1 Localization in Physics -- 1.2 Localization in Numerical Mathematics -- 2 Notation and Background in Linear Algebra and Graph Theory -- 3 Localization in Matrix Functions -- 3.1 Matrices with Decay -- 3.2 Decay Bounds for the Inverse -- 3.3 Decay Bounds for the Matrix Exponential -- 3.4 Decay Bounds for General Analytic Functions -- 3.4.1 Bounds for the Normal Case -- 3.4.2 Bounds for the Nonnormal Case -- 3.5 Bounds for Matrix Functions Defined by Integral Transforms -- 3.6 Functions of Structured Matrices -- 3.7 Some Generalizations -- 3.7.1 The Time-Ordered Exponential -- 3.8 Decal Algebras -- 3.9 Localization in Matrix Factorizations -- 3.10 Localization in the Unbounded Case -- 4 Applications -- 4.1 Applications in Numerical Linear Algebra -- 4.1.1 Linear Systems with Localized Solutions -- 4.1.2 Construction of Preconditioners -- 4.1.3 Localization and Eigenvalue Problems -- 4.1.4 Approximation of Matrix Functions -- 4.1.5 Approximation Based on Quadrature Rules -- 4.1.6 Error Bounds for Krylov Subspace Approximations -- 4.1.7 Exponentials of Stochastic Matrices -- 4.1.8 Exponential Integrators -- 4.2 Linear Scaling Methods for Electronic Structure Computations -- 4.3 Further Applications -- 4.3.1 Localized Solutions to Matrix Equations -- 4.3.2 Localization in Graph and Network Analysis -- 4.3.3 Log-Determinant Evaluation -- 4.3.4 Quantum Information Theory -- 5 Conclusions and Future Work -- References -- Groups and Symmetries in Numerical Linear Algebra -- 1 Introduction -- 1.1 Motivation for the Main Topics of the Lectures -- 2 Prelude: Introduction to Group Theory -- 2.1 Groups and Actions -- 2.2 Subgroups and Quotients -- 2.3 Homomorphisms and Exact Sequences -- 2.4 Products of Groups and Split Exact Sequences. 327 $a2.5 Domains in Computational Mathematics -- 3 Abelian Groups, Fourier Analysis, Lattices and Sampling -- 3.1 Introduction to Abelian Groups -- 3.1.1 Definition and Basic Properties -- 3.1.2 Topology -- 3.1.3 The Elementary Groups -- 3.2 Computing with FGAs -- 3.2.1 Abelian Categories -- 3.2.2 Free FGAs and Smith's Normal Form -- 3.2.3 General Homomorphisms -- 3.2.4 Hermite's Normal Form -- 3.2.5 Summary -- 3.3 Circulant Matrices and the Discrete Fourier Transform -- 3.4 Fourier Analysis on General LCAs -- 3.4.1 Functions on G -- 3.4.2 Shifts, Integrals and Convolutions -- 3.4.3 The Dual Group -- 3.4.4 The Fourier Transform -- 3.4.5 Schwartz Space and Tempered Distributions -- 3.4.6 Pullback and Pushforward of Functions on Groups -- 3.5 Duality of Subgroups and Quotients -- 3.5.1 Dual Homomorphisms -- 3.5.2 The Fundamental Duality Theorem -- 3.6 Lattices and Sampling -- 3.6.1 Pullback and Pushforward on Lattices -- 3.6.2 Choosing Coset Representatives -- 3.6.3 Sampling and Aliasing -- 3.7 The Fast Fourier Transform (FFT) -- 3.7.1 Heisenberg Groups and the Weil-Brezin Map -- 3.8 Lattice Rules -- 3.8.1 Computational Fourier Analysis on Rd -- 3.8.2 Eigenfunctions of the Continuous and Discrete Fourier Transforms -- 3.9 Boundaries, Mirrors and Kaleidoscopes -- 3.10 Cyclic Reduction -- 3.11 Preconditioning with Convolutional Operators -- 3.11.1 Matrix Multiplication by Diagonals -- 3.11.2 Preconditioning -- 4 Domain Symmetries and Non-commutative Groups -- 4.1 G-Equivariant Matrices -- 4.2 The Group Algebra -- 4.3 The Generalized Fourier Transform (GFT) -- 4.4 Applications to the Matrix Exponential -- 4.4.1 Example: Equilateral Triangle -- 4.4.2 Example: Icosahedral Symmetry -- 5 Concluding Remarks -- References. 330 $aFocusing on special matrices and matrices which are in some sense `near? to structured matrices, this volume covers a broad range of topics of current interest in numerical linear algebra. Exploitation of these less obvious structural properties can be of great importance in the design of efficient numerical methods, for example algorithms for matrices with low-rank block structure, matrices with decay, and structured tensor computations. Applications range from quantum chemistry to queuing theory. Structured matrices arise frequently in applications. Examples include banded and sparse matrices, Toeplitz-type matrices, and matrices with semi-separable or quasi-separable structure, as well as Hamiltonian and symplectic matrices. The associated literature is enormous, and many efficient algorithms have been developed for solving problems involving such matrices. The text arose from a C.I.M.E. course held in Cetraro (Italy) in June 2015 which aimed to present this fast growing field to young researchers, exploiting the expertise of five leading lecturers with different theoretical and application perspectives. 410 0$aC.I.M.E. Foundation Subseries ;$v2173 606 $aNumerical analysis 606 $aComputer science$xMathematics 606 $aNumerical Analysis$3https://scigraph.springernature.com/ontologies/product-market-codes/M14050 606 $aComputational Science and Engineering$3https://scigraph.springernature.com/ontologies/product-market-codes/M14026 615 0$aNumerical analysis. 615 0$aComputer science$xMathematics. 615 14$aNumerical Analysis. 615 24$aComputational Science and Engineering. 676 $a512.9434 700 $aBenzi$b Michele$4aut$4http://id.loc.gov/vocabulary/relators/aut$0785607 702 $aBini$b Dario$4aut$4http://id.loc.gov/vocabulary/relators/aut 702 $aKressner$b Daniel$4aut$4http://id.loc.gov/vocabulary/relators/aut 702 $aMunthe-Kaas$b Hans$4aut$4http://id.loc.gov/vocabulary/relators/aut 702 $aVan Loan$b Charles$4aut$4http://id.loc.gov/vocabulary/relators/aut 702 $aBenzi$b Michele$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aSimoncini$b Valeria$4edt$4http://id.loc.gov/vocabulary/relators/edt 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910166058103321 996 $aExploiting Hidden Structure in Matrix Computations: Algorithms and Applications$92283979 997 $aUNINA