Fast Parallel Matrix Inversion Algorithms

DOI10.1137/0205040zbMath0353.68063OpenAlexW2113097540WikidataQ56850701 ScholiaQ56850701MaRDI QIDQ4124326

Publication date: 1976

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0205040

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

Polyhedral techniques in combinatorial optimization: matchings and tours, The stochastic arrival problem, Oracle computations in parallel numerical linear algebra, Specified precision polynomial root isolation is in NC, Tensor and border rank of certain classes of matrices and the fast evaluation of determinant, inverse matrix, and eigenvalues, Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits, On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace, Determinant: Old algorithms, new insights, Iterative methods for the parallel solution of linear systems, Matching is as easy as matrix inversion, The complexity of elementary algebra and geometry, Complexity of parallel matrix computations, On the VLSI complexity of some arithmetic and numerical problems, Inversion Modulo Zero-Dimensional Regular Chains, Lower bounds for diophantine approximations, Quantum machine learning: a classical perspective, Types of depth and formula size, A VLSI fast solver for tridiagonal linear systems, The semantics and complexity of parallel programs for vector computations. I: A case study using Ada, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Algebraic secret sharing using privacy homomorphisms for IoT-based healthcare systems, Feasible arithmetic computations: Valiant's hypothesis, Parallel evaluation of the determinant and of the inverse of a matrix, Singular spaces of matrices and their application in combinatorics, Techniques for parallel manipulation of sparse matrices, Deformation techniques to solve generalised Pham systems, A Monte Carlo method for the parallel solution of linear systems, NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems, NC Algorithms for Weighted Planar Perfect Matching and Related Problems, On approximating the eigenvalues of stochastic matrices in probabilistic logspace, On parallel complexity of analytic functions, Membership in polynomial ideals over Q is exponential space complete, Systolic algorithm for the solution of dense linear equations, Minimisation of Multiplicity Tree Automata, Deterministic simulation of tape-bounded probabilistic Turing machine transducers, On the Descriptive Complexity of Linear Algebra, Unnamed Item, Phenotype space and kinship assignment for the simpson index, Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\), On uniform circuit complexity, Classifying the computational complexity of problems, Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits, Parallelism and fast solution of linear systems, On the complexity of simplifying quadratic forms, On tape-bounded probabilistic Turing machine acceptors, A complexity theory of efficient parallel algorithms, Parallel models of computation: An introductory survey, Generalised characteristic polynomials, Parallel solution of linear systems by repeated squaring, Efficient parallel algorithms for linear recurrence computation, Parallel algorithm for householder transformation with applications to Ill-conditioned problems, Computing multivariate polynomials in parallel, Parallel complexities and computations of cholesky's decomposition and QR factorization, Polynomial decomposition algorithms, ON THE MINIMAL POLYNOMIAL OF A MATRIX, Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic, Circuits for computing the GCD of two polynomials over an algebraic number field, Matrix inversion in RNC\(^ 1\), On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination, On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination, COMPUTATION OF A DETERMINANT AND A MATRIX PRODUCT IN CELLULAR AUTOMATA, Deterministic computation of the characteristic polynomial in the time of matrix multiplication, Parallel solution of Toeplitzlike linear systems, Parallel algebraic reductions among numerical problems, Sparse interpolation of symmetric polynomials, A survey of space complexity, On affine scaling algorithms for nonconvex quadratic programming, An improved parallel algorithm for computing the generalized inverse \(A^ +\), Matching theory -- a sampler: From Dénes König to the present, The unpredictable deviousness of models, Efficient algorithms for computing the characteristic polynomial in a domain, Parametrization of Newton's iteration for computations with structured matrices and applications, On the arithmetic operational complexity for solving Vandermonde linear equations, Fast and scalable parallel matrix computations with reconfigurable pipelined optical buses, A Gröbner free alternative for polynomial system solving, Unnamed Item, Unnamed Item, A lower bound for the shortest path problem, Parallel direct linear system solvers - a survey, Fast parallel algorithms for vandermonde determinants, An improved parallel processor bound in fast matrix inversion, Parallel computations in linear algebra, On the depth complexity of formulas, Factorization of polynomials given by arithmetic branching programs, Arithmetic Circuits: A Chasm at Depth 3, Unnamed Item, Unnamed Item, Algebraic Complexity Classes, Fast and efficient parallel solution of dense linear systems, Parallel algorithms and architectures for matrix multiplication, Successive matrix squaring algorithm for computing the Drazin inverse, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Bipartite Perfect Matching is in Quasi-NC, A new iterative Monte Carlo approach for inverse matrix problem, On computing the determinant in small parallel time using a small number of processors, Comparison of Accuracy and Scalability of Gauss--Newton and Alternating Least Squares for CANDECOMC/PARAFAC Decomposition, Minimum energy requirements of information transfer and computing, Upper bounds on the complexity of solving systems of linear equations, On the coefficients of the characteristic polynomial of a matrix, Computation of equilibria in noncooperative games, Spectral properties of some matrices close to the Toeplitz triangular form