Improved rounding for spline coefficients and knots

Grosse, Eric; Hobby, John D.

doi:10.1090/S0025-5718-1994-1240659-8

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 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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/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.