Fast parallel matrix and GCD computations
From MaRDI portal
Publication:4745254
DOI10.1016/S0019-9958(82)90766-5zbMath0507.68020OpenAlexW4210445513MaRDI QIDQ4745254
Joachim von zur Gathen, Allan Borodin, John E. Hopcrofts
Publication date: 1982
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(82)90766-5
parallel algorithmsdeterminantrank of matricesgreatest common divisor of polynomialsarbitrary fieldscharacteristic polynomial of matricesparallel Las Vegas algorithmssolutions of arbitrary systems of linear equations
Related Items (74)
Oracle computations in parallel numerical linear algebra ⋮ Specified precision polynomial root isolation is in NC ⋮ Factoring sparse multivariate polynomials ⋮ Fast parallel absolute irreducibility testing ⋮ Irreducibility of multivariate polynomials ⋮ Accurate approximate diagnosis of (controllable) stochastic systems ⋮ Polynomial division and its computational complexity ⋮ Algebraic complexity of computing polynomial zeros ⋮ The complexity of elementary algebra and geometry ⋮ Sequential and parallel complexity of approximate evaluation of polynomial zeros ⋮ A fast parallel algorithm to compute the rank of a matrix over an arbitrary field ⋮ Computer algebra: Past and future ⋮ Complexity of parallel matrix computations ⋮ Inversion in finite fields using logarithmic depth ⋮ Applications of matrix methods to the theory of lower bounds in computational complexity ⋮ Boolean circuits versus arithmetic circuits ⋮ Constructing a perfect matching is in random NC ⋮ Lower bounds for diophantine approximations ⋮ Formalisation of the computation of the echelon form of a matrix in Isabelle/HOL ⋮ On the computational complexity of the Abelian permutation group structure, membership and intersection problems ⋮ A logarithmic Boolean time algorithm for parallel polynomial division ⋮ Types of depth and formula size ⋮ A systolic algorithm for extended GCD computation ⋮ Parallel algorithms for solvable permutation groups ⋮ Parallel computation of polynomial GCD and some related parallel computations over abstract fields ⋮ Feasible arithmetic computations: Valiant's hypothesis ⋮ Parallel evaluation of the determinant and of the inverse of a matrix ⋮ The iterated mod problem ⋮ Structure and importance of logspace-MOD class ⋮ Matrix structures in parallel matrix computations ⋮ On parallel complexity of analytic functions ⋮ Markov chains and unambiguous automata ⋮ Decision Questions for Probabilistic Automata on Small Alphabets ⋮ Unnamed Item ⋮ How strong is Nisan's pseudo-random generator? ⋮ Parallelism and fast solution of linear systems ⋮ Analysis of Euclidean algorithms for polynomials over finite fields ⋮ Parallel models of computation: An introductory survey ⋮ Problems complete for \(\oplus L\) ⋮ On arithmetic branching programs ⋮ Subtree isomorphism is in random NC ⋮ Efficient algorithmic learning of the structure of permutation groups by examples ⋮ Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices ⋮ The price of query rewriting in ontology-based data access ⋮ 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\) ⋮ A practical approach to the secure computation of the Moore-Penrose pseudoinverse over the rationals ⋮ On the evaluation of the eigenvalues of a banded Toeplitz block matrix ⋮ Parallel solution of Toeplitzlike linear systems ⋮ Parallel algebraic reductions among numerical problems ⋮ The complexity of circuit value and network stability ⋮ Decomposition of algebras over finite fields and number fields ⋮ NC algorithms for real algebraic numbers ⋮ Computing the inertia of Bézout and Hankel matrices ⋮ Parametrization of Newton's iteration for computations with structured matrices and applications ⋮ Efficient parallel factorization and solution of structured and unstructured linear systems ⋮ Parallel output-sensitive algorithms for combinatorial and linear algebra problems ⋮ A randomized sublinear time parallel GCD algorithm for the EREW PRAM ⋮ Towards a quantum-resistant weak verifiable delay function ⋮ Improved processor bounds for combinatorial problems in RNC ⋮ Comparative Analysis of Random Generators ⋮ Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets ⋮ Fast parallel algorithms for polynomial division over an arbitrary field of constants ⋮ Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros ⋮ Fast and efficient solution of path algebra problems ⋮ Fast and efficient parallel solution of dense linear systems ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs ⋮ Division-free computation of subresultants using Bezout matrices ⋮ The enumerability of P collapses P to NC ⋮ The computational complexity of some problems of linear algebra ⋮ Spectral properties of some matrices close to the Toeplitz triangular form
This page was built for publication: Fast parallel matrix and GCD computations
