LOGARITHMIC DEPTH CIRCUITS FOR HERMITE INTERPOLATION
Date
1990-07-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We present a new parallel algorithm for Hermite interpolation. The
algorithm can be implemented using arithmetic-boolean circuits of
depth logarithmic and size polynomial in the input size. A
corresponding Boolean algorithm can be used to compute the coefficients
of the Hermite interpolating polynomial from binary representations of
evaluation points and derivatives over finite fields and number fields,
using a P-uniform family of circuits of depth logarithmic in the
input size and of polynomial size.
Description
Keywords
Computer Science