SIAM Journal on Computing · 1979 · 50 citations · 1 references
Mathematical ProgrammingParallel EvaluationEngineeringComputational Number TheoryOrthogonal PolynomialParallel Complexity TheoryAlgebraic MethodComputational ComplexityTime ComplexityParallel ProgrammingComputer ScienceMultivariate Polynomial PDiscrete MathematicsParallel ComputingParallel StepsDegree DApproximation TheoryMultivariate Approximation
We prove that any multivariate polynomial P of degree d that can be computed with $C(P)$ multiplications-divisions can be computed in $O(\log d \cdot \log C(P))$ parallel steps and $O(\log d)$ parallel multiplicative steps.
1
Fast Parallel Matrix Inversion Algorithms
L. Csanky · SIAM Journal on Computing · 1976 · 399 citations