Abstract
A fast parallel algorithm for rational interpolation based on orthogonal polynomials, which is suitable for both shared-memory and message-passing multiprocessor systems is proposed. In the shared-memory case with N + 1 identical processors, the algorithm requires 0(N log N) parallel arithmetic steps to construct all rational interpolants at once, where N +1 is the number of data points. Extensions to message-passing multiprocessor systems such as the hypercube are also discussed. The hypercube version of the algorithm requires 0(N log N) inter-processor communication overhead. Thus in effect, the algorithm constructs each rational interpolant using O(log N) parallel arithmetic and O(log N) communication steps.
Supported in part by NSF Grant No. DCR-8603722.
Supported in part by Lawrence Livermore National Laboratory, Contract No. LLNL-7526225 and the Nat~onal Science Foundation (and AFOSR) under Grant No. ECS84-06152.
Supported in part by NSF Grant No. DCR-8603722.
Supported in part by Lawrence Livermore National Laboratory, Contract No. LLNL-7526225 and the Nat~onal Science Foundation (and AFOSR) under Grant No. ECS84-06152.
Notes
Supported in part by NSF Grant No. DCR-8603722.
Supported in part by Lawrence Livermore National Laboratory, Contract No. LLNL-7526225 and the Nat~onal Science Foundation (and AFOSR) under Grant No. ECS84-06152.