Fast Parallel Matrix and GCD Computations.

Abstract

We present parallel algorithms to compute the determinant and characteristics polynomial of nxn-matrices and the gcd of polynomials of degree less than or equal n. The algorithms use parallel time O(log to the 2nd power n) and a polynomial number of processors. We also give a fast parallel Monte Carlo algorithm for the rank of matrices. All algorithms work over arbitrary fields. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1982
Accession Number
ADA113577

Entities

People

  • Allan Borodin
  • Joachim Von Zur Gathen
  • John E. Hopcroft

Organizations

  • Cornell University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computations
  • Computer Science
  • Computers
  • Elimination
  • Equations
  • Fast Fourier Transforms
  • Inversion
  • Monte Carlo Method
  • New York
  • Parallel Computing
  • Polynomials
  • Probability
  • Rational Functions
  • Theorems
  • Vector Spaces

Fields of Study

  • Mathematics

Readers

  • Computer Programming and Software Development.
  • Graph Algorithms and Convex Optimization.