Efficient parallel algorithms for linear recurrence computation

DOI10.1016/0020-0190(82)90081-3zbMath0487.68028OpenAlexW2088465126MaRDI QIDQ1165573

Michael S. Paterson, Zvi Galil, Richard E. Ladner, Albert G. Greenberg

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(82)90081-3

zbMATH Keywords

parallel algorithmsparallel processingconcurrencyarithmetic circuitexponent of matrix multiplicationlinear recurrence computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25) Algorithms in computer science (68W99)

Related Items

A fast algorithm for scalar Nevanlinna-Pick interpolation, OPTIMAL PARALLEL PREFIX ON MESH ARCHITECTURES, The iterated mod problem, Efficient simulation of circuits by EREW PRAMs, Parallel prefix computation with few processors, Limited width parallel prefix circuits, Fast computation of continued fractions

Cites Work

• Unnamed Item
• Gaussian elimination is not optimal
• Parallel Prefix Computation
• Parallel Solution of Recurrence Problems
• Time and Parallel Processor Bounds for Linear Recurrence Systems
• Fast Parallel Matrix Inversion Algorithms
• The Complexity of Parallel Evaluation of Linear Recurrences
• On Relating Time and Space to Size and Depth
• Solving Triangular Systems on a Parallel Computer
• A Survey of Parallel Algorithms in Numerical Linear Algebra