Solving linear systems of equations with randomization, augmentation and aggregation (Q454828): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Pan, Victor Y. / rank | |||
Property / author | |||
Property / author: Pan, Victor Y. / rank | |||
Normal rank | |||
Property / review text | |||
The paper concentrates on computing an approximation to the basis of the null space of a given rectangular (possibly rank deficient and/or ill-conditioned) matrix. Classical algorithms for solving such problems are usually based on a singular value decomposition, the LU or QR factorization. However, these techniques do not preserve a possible sparse structure of the matrix during the computation. Thus, algorithms are derived that are able to do so. They are based on randomization of different types (e.g. randomized preconditioning), augmentation and aggregation. These algorithms are then extended to solve nonhomogeneous systems of linear equations with a nonsingular and possibly ill-conditioned matrix. A theoretical analysis is included. Several numerical experiments illustrate behaviour of the algorithms. | |||
Property / review text: The paper concentrates on computing an approximation to the basis of the null space of a given rectangular (possibly rank deficient and/or ill-conditioned) matrix. Classical algorithms for solving such problems are usually based on a singular value decomposition, the LU or QR factorization. However, these techniques do not preserve a possible sparse structure of the matrix during the computation. Thus, algorithms are derived that are able to do so. They are based on randomization of different types (e.g. randomized preconditioning), augmentation and aggregation. These algorithms are then extended to solve nonhomogeneous systems of linear equations with a nonsingular and possibly ill-conditioned matrix. A theoretical analysis is included. Several numerical experiments illustrate behaviour of the algorithms. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Iveta Hnetynkova / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65F22 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 15A06 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 15A03 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 15A12 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65F08 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6092445 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
system of linear equations | |||
Property / zbMATH Keywords: system of linear equations / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
null space | |||
Property / zbMATH Keywords: null space / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
rank | |||
Property / zbMATH Keywords: rank / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
condition number | |||
Property / zbMATH Keywords: condition number / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
preconditioning | |||
Property / zbMATH Keywords: preconditioning / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
randomization | |||
Property / zbMATH Keywords: randomization / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
augmentation | |||
Property / zbMATH Keywords: augmentation / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
aggregation | |||
Property / zbMATH Keywords: aggregation / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
algorithm | |||
Property / zbMATH Keywords: algorithm / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
singular value decomposition | |||
Property / zbMATH Keywords: singular value decomposition / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
LU or QR factorization | |||
Property / zbMATH Keywords: LU or QR factorization / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
ill-conditioned matrix | |||
Property / zbMATH Keywords: ill-conditioned matrix / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
numerical experiments | |||
Property / zbMATH Keywords: numerical experiments / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.laa.2012.07.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2087182773 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4314299 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Condition Numbers of Gaussian Random Matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Estimating Extremal Eigenvalues and Condition Numbers of Matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Probability That a Numerical Analysis Problem is Difficult / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A probabilistic remark on algebraic program testing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2760174 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eigenvalues and Condition Numbers of Random Matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Symbolic and numeric methods for exploiting structure in constructing resultant matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tails of Condition Number Distributions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of multiplication with vectors for structured matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5689624 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Accuracy and Stability of Numerical Algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algebraic methods for Toeplitz-like matrices and operators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Displacement ranks of matrices and linear equations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Methods of aggregation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Multivariate polynomials, duality, and structured matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Computations with Dense Structured Matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the existence and computation of rank-revealing LU factorizations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2760974 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3086667 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Schur aggregation for linear systems and determinants / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Additive preconditioning for matrix computations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new error-free floating-point summation algorithm / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Randomized preprocessing of homogeneous linear systems of equations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Advancing Matrix Computations with Randomized Preprocessing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Randomized preprocessing versus pivoting / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matrix computations and polynomial root-finding with preprocessing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Additive preconditioning, eigenspaces, and the inverse iteration / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4220521 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Stabilized Superfast Solver for Nonsymmetric Toeplitz Systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A stabilized superfast solver for indefinite Hankel systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effect of small rank modification on the condition number of a matrix / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3851616 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 18:42, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Solving linear systems of equations with randomization, augmentation and aggregation |
scientific article |
Statements
Solving linear systems of equations with randomization, augmentation and aggregation (English)
0 references
10 October 2012
0 references
The paper concentrates on computing an approximation to the basis of the null space of a given rectangular (possibly rank deficient and/or ill-conditioned) matrix. Classical algorithms for solving such problems are usually based on a singular value decomposition, the LU or QR factorization. However, these techniques do not preserve a possible sparse structure of the matrix during the computation. Thus, algorithms are derived that are able to do so. They are based on randomization of different types (e.g. randomized preconditioning), augmentation and aggregation. These algorithms are then extended to solve nonhomogeneous systems of linear equations with a nonsingular and possibly ill-conditioned matrix. A theoretical analysis is included. Several numerical experiments illustrate behaviour of the algorithms.
0 references
system of linear equations
0 references
null space
0 references
rank
0 references
condition number
0 references
preconditioning
0 references
randomization
0 references
augmentation
0 references
aggregation
0 references
algorithm
0 references
singular value decomposition
0 references
LU or QR factorization
0 references
ill-conditioned matrix
0 references
numerical experiments
0 references
0 references
0 references