Article

Article title TIME COMPLEXITY OF PARALLEL PIECEWISE POLYNOMIAL CALCULATION OF FUNCTION EVALUATION
Authors Ya.E. Romm, I.I. Stakhovskaya
Section SECTION III. ALGORITHMIC AND THE SOFTWARE
Month, Year 05, 2013 @en
Index UDC 519.6:681.3
DOI
Abstract In the article the algorithms and the time complexity evaluation for parallel piecewise polynomial calculation of univariate functions on a base of Newton"s interpolating polynomials are resented. A polynomial degree and a number of subintervals are algorithmically variated for an a priori different given error bound; the massive parallel form of the computational algorithm was proposed. It was depicted in a model of nonbranching parallel program that we can achieve еvaluation of time complexity T(R) = O (log2 N), where N is a prescribed limit of polynomial degree variation and processor number complies a maximum number of subintervals and checkpoints. For standard functions it is T(1) = O(1) . Parallel approximate computing of derivatives and integrals is available synchronously along with the polynomial approximation of a function.

Download PDF

Keywords Piecewise polynomial calculating of functions; parallel computation; time complexity; Newton's interpolating polynomials.
References

Comments are closed.