Cubic Spline Interpolation by Solving a Single Recurrence Equation instead of a Triangular Matrix

Professor Peter Revesz
Computer Science and Engineering
University of Nebraska-Lincoln
USA
E-mail: revesz.nebraska@gmail.com
 

Abstract: The cubic spline interpolation method is probably the most widely-used polynomial interpolation method for functions of one variable. However, the cubic spline method requires solving a triangular matrix-vector equation with an O(n) computational time complexity where n is the number of data measurements. Even an O(n) time complexity may be too much in some time-ciritical applications, such as continuously estimating and updating the flight paths of moving objects. This paper shows that under certain boundary conditions the triangular matrix solving step of the cubic spline method could be entirely eliminated and instead the coefficients of the unknown cubic polynomials can be found by solving a single recurrence equation in much faster time.

Short biography: Peter Revesz holds a Ph.D. degree in Computer Science from Brown University. He was a postdoctoral fellow at the University of Toronto before joining the University of Nebraska-Lincoln, where he is a professor in the Department of Computer Science and Engineering. His current research interests are bioinformatics, geoinformatics, databases and data mining. He is the author of several books, including the textbook Introduction to Databases: From Biological to Spatio-Temporal (Springer, 2010). He held visiting appointments at the IBM T.J. Watson Research Center, INRIA, the University of Hasselt, the Max Planck Institute for Computer Science, the University of Athens, and the U.S. Department of State. He is a recipient of a National Science Foundation CAREER award, and a J. William Fulbright, an Alexander von Humboldt, and a Jefferson Science Fellowship.