In:
ACM SIGARCH Computer Architecture News, Association for Computing Machinery (ACM), Vol. 18, No. 3b ( 1990-09), p. 121-131
Abstract:
We show how to transform the B-spline curve and surface fitting problems into suffix computations of continued fractions. Then a parallel substitution scheme is introduced to compute the suffix values on a newly proposed mesh-of-unshuffle network. The derived parallel algorithm allows the curve interpolation through n points to be solved in O (log n ) time using Θ( n /log n processors and allows the surface interpolation through m × n points to be solved in O (log m log n ) time using Θ( mn /(log m log n )) processors. Both interpolation algorithms are cost-optimal for their respective problems. Besides, the surface fitting problem can be even faster solved in O (log m + log n ) time if Θ( mn ) processors are used in the network.
Type of Medium:
Online Resource
ISSN:
0163-5964
DOI:
10.1145/255129.255147
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
1990
detail.hit.zdb_id:
2088489-8
detail.hit.zdb_id:
186012-4
Permalink