Structured matrices and polynomials. Unified superfast algorithms
algorithmsbibliographycomputer algebradecodingdisplacement rankdivide-and-conquer methodencodingexercisesNehari problemsNevanlinna-Pick problemNewton's iterationnumerical linear algebrapolynomialsrational interpolationrecursive matrix factorizationstructured matricessymbolic operator approachtextbook
Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Direct numerical methods for linear systems and matrix inversion (65F05) Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20) Symbolic computation and algebraic computation (68W30)
The author presents key techniques and ideas to unify various computations with matrices and polynomials, which are the backbones of modern computations. One of his goals is to reveal the correlation between computations with polynomials and structured matrices. A substantial part of computer algebra using structured matrices is covered. Close ties between structured matrices and the Nevanlinna-Pick and Nehari problems of rational interpolation and approximation are observed. Apart from unifying the study of matrices and polynomials, the author focuses on the design of effective algorithms unified over various classes of structured matrices. The basis tool is the displacement rank approach to computations with structured matrices. The main framework for the presentation of some highly effective algorithms is the symbolic operator approach (an alternative and complementary method for unifying matrix structure). The author presents advanced hot topics and even new results in a structured form. Most of the material is covered with proofs, derivations and technical details, but the long proofs are completely avoided. The book consists of seven chapters and a bibliography of 371 books, papers, etc. The main topics which are covered are: (i) computations with structured matrices and polynomials; (ii) computer algebra and numerical linear algebra; (iii) matrix structures of various classes; (iv) structured matrices and Navanlinna-Pick and Nehari problems; (v) displacement rank approach; (vi) algorithmic transformation techniques; (vii) divide-and-conquer method and recursive matrix factorization; (viii) Newton's iteration in numerical and algebraic versions; (ix) superfast and memory efficient algorithms for structured matrix computations, numerical rational interpolation and approximation, loss-resilient encoding/decoding, etc. At the end of each Chapter a lot of good exercises are added.
- New homotopic/factorization and symmetrization techniques for Newton's and Newton/structured iteration
- Fast conversion algorithms for orthogonal polynomials
- Structured matrices and Newton's iteration: unified approach
- Symbolic and numeric methods for exploiting structure in constructing resultant matrices
- Accurate solutions of product linear systems associated with rank-structured matrices
- A periodic qd-type reduction for computing eigenvalues of structured matrix products to high relative accuracy
- Fast structured matrix computations: tensor rank and Cohn-Umans method
- An improved computationally efficient method for finding the Drazin inverse
- An efficient method to compute the Moore-Penrose inverse
- Structured matrices in numerical linear algebra. Analysis, algorithms and applications. Selected papers based on the presentations at the INdAM meeting, Cortona, Italy, September 4--8, 2017
- Displacement structure of \(W\)-weighted Drazin inverse \(A_{d,W}\) and its perturbation
- Improved algorithms for computing determinants and resultants
- Newton-like iteration based on a cubic polynomial for structured matrices
- Jet functions having indefinite Carathéodory-Pick matrices
- Computation of approximate polynomial GCDs and an extension
- Displacement rank of the Drazin inverse
- Randomized preprocessing versus pivoting
- Superfast solution of Toeplitz systems based on syzygy reduction
- A nearly optimal algorithm to decompose binary forms
- Computing eigenvalues of quasi-generalized Vandermonde matrices to high relative accuracy
- The asymptotic distribution of the condition number for random circulant matrices
- Fast sixth-order algorithm based on the generalized Cayley transform for the Zakharov-Shabat system associated with nonlinear Schrödinger equation
- Algorithms for simultaneous Hermite-Padé approximations
- Matrix completion for matrices with low-rank displacement
- Trapdoor delegation and HIBE from middle-product LWE in standard model
- The spectral connection matrix for classical orthogonal polynomials of a single parameter
- Fast Hermite interpolation and evaluation over finite fields of characteristic two
- Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
- Real polynomial root-finding by means of matrix and polynomial iterations
- Numerically safe Gaussian elimination with no pivoting
- A fast direct method for block triangular Toeplitz-like with tri-diagonal block systems from time-fractional partial differential equations
- Computations with quasiseparable polynomials and matrices
- Schur aggregation for linear systems and determinants
- The amended DSeSC power method for polynomial root-finding
- Multi-dimensional Capon spectral estimation using discrete Zhang neural networks
- The fast Slepian transform
- Automating algorithm selection: checking for matrix properties that can simplify computations
- Fast systematic encoding of multiplicity codes
- Additive preconditioning and aggregation in matrix computations
- Fast algorithms for Toeplitz and Hankel matrices
- Resultant matrices and inversion of Bézoutians
- Root-squaring with DPR1 matrices
- A fast method to block-diagonalize a Hankel matrix
- Approximate factorization of multivariate polynomials using singular value decomposition
- Estimating the norms of random circulant and Toeplitz matrices and their inverses
- Backward error analysis of the extended iterative refinement or improvement algorithm for solving ill conditioned linear system
- The stability of formulae of the Gohberg-Semencul-Trench type for Moore-Penrose and group inverses of Toeplitz matrices
- Hardware-friendly compression and hardware acceleration for transformer: a survey
- A note on computing the inverse of a triangular Toeplitz matrix
- How bad are Vandermonde matrices?
- Inverting structured operators related to Toeplitz plus Hankel operators
- An accelerated divide-and-conquer algorithm for the bidiagonal SVD problem
- scientific article; zbMATH DE number 5872171 (Why is no real title available?)
- Generalizing block LU factorization: a lower-upper-lower block triangular decomposition with minimal off-diagonal ranks
- New studies of randomized augmentation and additive preprocessing
- Hyperbolic Householder Algorithms for Factoring Structured Matrices
- Additive Preconditioning for Matrix Computations
- An Algorithm for Transforming Regular Chain into Normal Chain
- The Schur aggregation and solving ill conditioned linear systems: the convergence theorem
- Wiener-Hopf and spectral factorization of real polynomials by Newton's method
- Modified SMS method for computing outer inverses of Toeplitz matrices
- scientific article; zbMATH DE number 1350351 (Why is no real title available?)
- scientific article; zbMATH DE number 493126 (Why is no real title available?)
- scientific article; zbMATH DE number 691245 (Why is no real title available?)
- Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons
- Solving linear systems of equations with randomization, augmentation and aggregation
- Simple and nearly optimal polynomial root-finding by means of root radii approximation
- Fast matrix multiplication and its algebraic neighbourhood
- Sum-of-squares optimization without semidefinite programming
- The generalized reciprocal super Catalan matrix
- Toeplitz matrices for LTI systems, an illustration of their application to Wiener filters and estimators
- Transformations of matrix structures work again
- Optimal designs for rational function regression
- The reciprocal super Catalan matrix
- A variant of the reciprocal super Catalan matrix
- Accurate computation of generalized eigenvalues of regular SR-BP pairs
- Dual certificates and efficient rational sum-of-squares decompositions for polynomial optimization over compact sets
- Displacement structure of the core inverse
- Random Toeplitz matrices: The condition number under high stochastic dependence
- Derivation and analysis of fast bilinear algorithms for convolution
- Studying new generalizations of max-min matrices with a novel approach
- A qd-type method for computing generalized singular values of BF matrix pairs with sign regularity to high relative accuracy
- Fast approximate computations with Cauchy matrices and polynomials
- On matrices with displacement structure: generalized operators and faster algorithms
- New progress in real and complex polynomial root-finding
- Homotopic residual correction processes
- Fast approximate inversion of a block triangular Toeplitz matrix with applications to fractional sub-diffusion equations.
- Efficient Identification of Butterfly Sparse Matrix Factorizations
- Nearly optimal computations with structured matrices
- Matrix structure and loss-resilient encoding/decoding
- Split algorithms for skewsymmetric Toeplitz matrices with arbitrary rank profile
- Iterative inversion of structured matrices
- A faster interior-point method for sum-of-squares optimization
- Generalized Matrix Nearness Problems
- Elimination ideal and bivariate resultant over finite fields
- Infinite triangular matrices, \(q\)-Pascal matrices, and determinantal representations
- Arithmetic circuits, structured matrices and (not so) deep learning
- Higher-order de Branges-Rovnyak and sub-Bergman spaces
- Memoryless block transceivers with minimum redundancy based on Hartley transforms
- High-order lifting for polynomial Sylvester matrices
This page was built for publication: Structured matrices and polynomials. Unified superfast algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2760974)
