Efficient parallel algorithms for linear recurrence computation

DOI10.1016/0020-0190(82)90081-3MaRDI QIDQ1165573zbMATH OpenOpenAlexFDO

Authors Richard E. Ladner, Michael S. Paterson, Zvi Galil, A. 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

arithmetic circuitconcurrencyexponent of matrix multiplicationlinear recurrence computationparallel algorithmsparallel processing

Mathematics Subject Classification ID

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

Cites work

• A Survey of Parallel Algorithms in Numerical Linear Algebra
• Fast Parallel Matrix Inversion Algorithms
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• On Relating Time and Space to Size and Depth
• Parallel Prefix Computation
• Parallel Solution of Recurrence Problems
• Solving Triangular Systems on a Parallel Computer
• The Complexity of Parallel Evaluation of Linear Recurrences
• Time and Parallel Processor Bounds for Linear Recurrence Systems

Cited in

(7)

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

This page was built for publication: Efficient parallel algorithms for linear recurrence computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1165573)