Affordable Access

Solving linear systems of equations with randomization, augmentation and aggregation

Authors
Journal
Linear Algebra and its Applications
0024-3795
Publisher
Elsevier
Publication Date
Volume
437
Issue
12
Identifiers
DOI: 10.1016/j.laa.2012.07.002
Keywords
  • Linear Systems Of Equations
  • Rank
  • Numerical Rank
  • Randomization
  • Augmentation
  • Aggregation
Disciplines
  • Computer Science

Abstract

Abstract Seeking a basis for the null space of a rectangular and possibly rank deficient and ill conditioned matrix we apply randomization, augmentation, and aggregation to reduce our task to computations with well conditioned matrices of full rank. Our algorithms avoid pivoting and orthogonalization, preserve matrix structure and sparseness, and in the case of an ill conditioned input perform only a small part of the computations with high accuracy. We extend the algorithms to the solution of nonhomogeneous nonsingular ill conditioned linear systems of equations whose matrices have small numerical nullities. Our estimates and experiments show dramatic progress versus the customary matrix algorithms where the input matrices are rank deficient or ill conditioned. Our study can be of independent technical interest: we extend the known results on conditioning of random matrices to randomized preconditioning, estimate the condition numbers of randomly augmented matrices, and link augmentation to aggregation as well as homogeneous to nonhomogeneous linear systems of equations.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Solving systems of sparse linear equations

on Advances in Engineering Softwa... Jan 01, 1984

Solving systems of linear fuzzy equations

on Fuzzy Sets and Systems Jan 01, 1991

Solving linear systems of equations

on Signal Processing Jan 01, 1993
More articles like this..