## Improved rounding for spline coefficients and knots

HTML articles powered by AMS MathViewer

- by Eric Grosse and John D. Hobby PDF
- Math. Comp.
**63**(1994), 175-194 Request permission

## 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.## References

- L. Babai,
*On Lovász’ lattice reduction and the nearest lattice point problem*, Combinatorica**6**(1986), no. 1, 1–13. MR**856638**, DOI 10.1007/BF02579403 - 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**, DOI 10.1137/0908003 - Carl de Boor,
*Good approximation by splines with variable knots. II*, Conference on the Numerical Solution of Differential Equations (Univ. Dundee, Dundee, 1973) Lecture Notes in Math., Vol. 363, Springer, Berlin, 1974, pp. 12–20. MR**0431606**
C. de Boor and J. R. Rice, - David L. B. Jupp,
*Approximation to data by splines with free knots*, SIAM J. Numer. Anal.**15**(1978), no. 2, 328–343. MR**488884**, DOI 10.1137/0715022 - 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**, DOI 10.1007/BF02128669
B. A. LaMacchia, - 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**, DOI 10.1007/BF01457454 - 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**, DOI 10.1093/imanum/11.3.393 - 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**, DOI 10.1090/S0025-5718-1989-0969492-7 - C.-P. Schnorr,
*A hierarchy of polynomial time lattice basis reduction algorithms*, Theoret. Comput. Sci.**53**(1987), no. 2-3, 201–224. MR**918090**, DOI 10.1016/0304-3975(87)90064-8 - C.-P. Schnorr,
*A more efficient algorithm for lattice basis reduction*, J. Algorithms**9**(1988), no. 1, 47–62. MR**925597**, DOI 10.1016/0196-6774(88)90004-1 - 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**, DOI 10.1007/3-540-54458-5_{5}1
N. L. Schryer, - Larry L. Schumaker,
*Spline functions: basic theory*, Pure and Applied Mathematics, John Wiley & Sons, Inc., New York, 1981. MR**606200**

*Least squares cubic spline approximation*. II:

*variable knots*, Technical report, CSD TR 21, Purdue Univ., Lafayette, IN, 1968. 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. 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.

*Basis reduction algorithms and subset sum problems*, Master’s thesis, EECS Dept., Massachusetts Institute of Technology, 1991.

*SSAF-smooth spline approximations to functions*, Technical report, AT&T Bell Laboratories CSTR 131, 1986.

*TIGER/LINE census files*, 1990,

*technical documentation*, Technical report, Bureau of the Census, U. S. Dept. of Commerce, Washington, D.C., 1991. 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. 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.

## Additional Information

- © Copyright 1994 American Mathematical Society
- Journal: Math. Comp.
**63**(1994), 175-194 - MSC: Primary 65D07
- DOI: https://doi.org/10.1090/S0025-5718-1994-1240659-8
- MathSciNet review: 1240659