Improved rounding for spline coefficients and knots

Authors:
Eric Grosse and John D. Hobby

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

MSC:
Primary 65D07

MathSciNet review:
1240659

Full-text PDF Free Access

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), no. 1, 1–13. MR**856638**, 10.1007/BF02579403**[2]**Petter Bjørstad and Eric Grosse,*Conformal mapping of circular arc polygons*, SIAM J. Sci. Statist. Comput.**8**(1987), no. 1, 19–32. MR**873921**, 10.1137/0908003**[3]**Carl de Boor,*Good approximation by splines with variable knots. II*, Conference on the Numerical Solution of Differential Equations (Univ. Dundee, Dundee, 1973) Springer, Berlin, 1974, pp. 12–20. Lecture Notes in Math., Vol. 363. MR**0431606****[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]**David L. B. Jupp,*Approximation to data by splines with free knots*, SIAM J. Numer. Anal.**15**(1978), no. 2, 328–343. MR**488884**, 10.1137/0715022**[8]**J. C. Lagarias, H. W. Lenstra Jr., and C.-P. Schnorr,*Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice*, Combinatorica**10**(1990), no. 4, 333–348. MR**1099248**, 10.1007/BF02128669**[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), no. 4, 515–534. MR**682664**, 10.1007/BF01457454**[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), no. 3, 393–409. MR**1118964**, 10.1093/imanum/11.3.393**[12]**G. Meinardus, G. Nürnberger, M. Sommer, and H. Strauss,*Algorithms for piecewise polynomials and splines with free knots*, Math. Comp.**53**(1989), no. 187, 235–247. MR**969492**, 10.1090/S0025-5718-1989-0969492-7**[13]**C.-P. Schnorr,*A hierarchy of polynomial time lattice basis reduction algorithms*, Theoret. Comput. Sci.**53**(1987), no. 2-3, 201–224. MR**918090**, 10.1016/0304-3975(87)90064-8**[14]**C.-P. Schnorr,*A more efficient algorithm for lattice basis reduction*, J. Algorithms**9**(1988), no. 1, 47–62. MR**925597**, 10.1016/0196-6774(88)90004-1**[15]**C.-P. Schnorr and M. Euchner,*Lattice basis reduction: improved practical algorithms and solving subset sum problems*, Fundamentals of computation theory (Gosen, 1991) Lecture Notes in Comput. Sci., vol. 529, Springer, Berlin, 1991, pp. 68–85. MR**1136071**, 10.1007/3-540-54458-5_51**[16]**N. L. Schryer,*SSAF-smooth spline approximations to functions*, Technical report, AT&T Bell Laboratories CSTR 131, 1986.**[17]**Larry L. Schumaker,*Spline functions: basic theory*, John Wiley & Sons, Inc., New York, 1981. Pure and Applied Mathematics; A Wiley-Interscience Publication. MR**606200****[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:
http://dx.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