Improved rounding for spline coefficients and knots

Authors:
Eric Grosse and John D. Hobby

Journal:
Math. Comp. **63** (1994), 175-194

MSC:
Primary 65D07

DOI:
https://doi.org/10.1090/S0025-5718-1994-1240659-8

MathSciNet review:
1240659

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: When representing the coefficients and knots of a spline using only small integers, independently rounding each infinite-precision value is not the best strategy. We show how to build an affine model for the error expanded about the optimal full-precision free-knot or parameterized spline, then use the Lovász basis reduction algorithm to select a better rounding. The technique could be used for other situations in which a quadratic error model can be computed.

**[1]**L. Babai,*On Lovász' lattice reduction and the nearest lattice point problem*, Combinatorica**6**(1986), 1-13. MR**856638 (88a:68049)****[2]**P. E. Bjørstad and E. H. Grosse,*Conformal mapping of circular arc polygons*, SIAM J. Sci. Statist. Comput.**8**(1987), 19-32. MR**873921 (88d:30010)****[3]**C. de Boor,*Good approximation by splines with variable knots*. II, Numerical Solution of Differential Equations (G. A. Watson, ed.), Springer-Verlag, New York, 1974, pp. 12-20. MR**0431606 (55:4603)****[4]**C. de Boor and J. R. Rice,*Least squares cubic spline approximation*. II:*variable knots*, Technical report, CSD TR 21, Purdue Univ., Lafayette, IN, 1968.**[5]**J. E. Dennis, Jr., D. M. Gay, and R. E. Welch,*An adaptive nonlinear least squares algorithm*, ACM Trans. Math. Software**7**(1981), 348-368, 369-383.**[6]**F. N. Fritsch and G. M. Nielson,*On the problem of determining the distance between parametric curves*, Technical report, Lawrence Livermore National Laboratory UCRL-JC-105408, 1990.**[7]**D. L. B. Jupp,*Approximation to data by splines with free knots*, SIAM J. Numer. Anal.**15**(1978), 328-343. MR**488884 (81e:41011)****[8]**J. C. Lagarias, H. W. Lenstra, Jr., and C. P. Schnorr,*Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal*, Combinatorica**10**(1990), 333-348. MR**1099248 (92a:11075)****[9]**B. A. LaMacchia,*Basis reduction algorithms and subset sum problems*, Master's thesis, EECS Dept., Massachusetts Institute of Technology, 1991.**[10]**A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász,*Factoring polynomials with rational coefficients*, Math. Ann.**261**(1982), 515-534. MR**682664 (84a:12002)****[11]**P. D. Loach and A. J. Wathen,*On the best least squares approximation of continuous functions using linear splines with free knots*, IMA J. Numer. Anal.**11**(1991), 393-409. MR**1118964 (93b:65016)****[12]**B. Meinardus, G. Nürnberger, M. Sommer, and H. Strauss,*Algorithms for piecewise polynomials and splines with free knots*, Math. Comp.**53**(1989), 235-247. MR**969492 (90d:65033)****[13]**C. P. Schnorr,*A hierarchy of polynomial time lattice basis reduction algorithms*, Theoret. Comput. Sci.**53**(1987), 201-224. MR**918090 (89h:11085)****[14]**-,*A more efficient algorithm for lattice basis reduction*, J. Algorithms**9**(1988), 47-62. MR**925597 (89h:11086)****[15]**C. P. Schnorr and M. Euchner,*Lattice basis reduction*:*Improved practical algorithms and solving subset sum problems*, Proc. of Fundamentals of Comput. Theory '91, Lecture Notes in Comput. Sci., Springer-Verlag, New York, 1991. MR**1136071****[16]**N. L. Schryer,*SSAF-smooth spline approximations to functions*, Technical report, AT&T Bell Laboratories CSTR 131, 1986.**[17]**L. L. Schumaker,*Spline functions*:*Basic theory*, Wiley, New York, 1981. MR**606200 (82j:41001)****[18]***TIGER/LINE census files*, 1990,*technical documentation*, Technical report, Bureau of the Census, U. S. Dept. of Commerce, Washington, D.C., 1991.**[19]**P. van Emde Boas,*Another NP-complete partition problem and the complexity of computing short vectors in a lattice*, Report 81-04, Math. Institute, Univ. of Amsterdam, 1981.**[20]**K. Wall and P.-E. Danielsson,*A fast sequential method for polygonal approximation of digitized curves*, Computer Vision, Graphics, and Image Processing, vol. 28, 1984, pp. 220-227.

Retrieve articles in *Mathematics of Computation*
with MSC:
65D07

Retrieve articles in all journals with MSC: 65D07

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1994-1240659-8

Keywords:
Free-knot splines,
parameterized splines,
rounding,
closest lattice point,
compression

Article copyright:
© Copyright 1994
American Mathematical Society