More Web Proxy on the site http://driver.im/

research-article

Algorithm 1031: MQSI—Monotone Quintic Spline Interpolation

Authors:

Layne T. Watson,

William ThackerAuthors Info & Claims

ACM Transactions on Mathematical Software, Volume 49, Issue 1

Article No.: 6, Pages 1 - 17

https://doi.org/10.1145/3570157

Published: 21 March 2023 Publication History

Abstract

MQSI is a Fortran 2003 subroutine for constructing monotone quintic spline interpolants to univariate monotone data. Using sharp theoretical monotonicity constraints, first and second derivative estimates at data provided by a quadratic facet model are refined to produce a univariate C² monotone interpolant. Algorithm and implementation details, complexity and sensitivity analyses, usage information, a brief performance study, and comparisons with other spline approaches are included.

Supplementary Material

PDF File (3570157.pdf)

Download
15.80 KB

References

[1]

M. Abbas, A. A. Majid, and J. M. Ali. 2012. Monotonicity-preserving C² rational cubic spline for monotone data. Appl. Math. Comput. 219, 6 (2012), 2885–2895.

[2]

T. Berglund, A. Brodnik, H. Jonsson, M. Staffanson, and I. Soderkvist. 2009. Planning smooth and obstacle-avoiding B-spline paths for autonomous mining vehicles. IEEE Trans. Autom. Sci. Eng. 7, 1 (2009), 167–172.

[3]

A. Brennan. 2020. Measure, modulation and metadesign: NC fabrication in industrial design and architecture. J. Des. Hist. 33, 1 (2020), 66–82.

[4]

K. W. Cameron, A. Anwar, Y. Cheng, L. Xu, B. Li, U. Ananth, J. Bernard, C. Jearls, T. C. H. Lux, Y. Hong, L. T. Watson, and A. R. Butt. 2019. MOANA: modeling and analyzing I/O variability in parallel system experimental design. IEEE Trans. Parallel Distrib. Syst. 30, 8 (2019), 1843–1856.

[5]

P. Costantini. 1986. On monotone and convex spline interpolation. Math. Comput. 46, 173 (1986), 203–214.

[6]

P. Costantini. 1997. Algorithm 770: BVSPIS – A package for computing boundary-valued shape-preserving interpolating splines. ACM Trans. Math. Softw. 23, 2 (1997), 252–254.

Digital Library

[7]

P. Costantini. 1997. Boundary-valued shape-preserving interpolating splines. ACM Trans. Math. Softw. 23, 2 (1997), 229–251.

Digital Library

[8]

I. Cravero and C. Manni. 2003. Shape-preserving interpolants with high smoothness. J. Computat. Appl. Math. 157, 2 (2003), 383–405.

Digital Library

[9]

R. Delbourgo and J. A. Gregory. 1983. C² rational quadratic spline interpolation to monotonic data. IMA J. Numer. Anal. 3, 2 (1983), 141–152.

[10]

R. A. DeVore. 1977. Monotone approximation by splines. SIAM J. Math. Anal. 8, 5 (1977), 891–905.

Digital Library

[11]

R. L. Dougherty, A. Edelman, and J. M. Hyman. 1989. Nonnegativity-, monotonicity- convexity-preserving cubic and quintic Hermite interpolation. Math. Comput. 52, 186 (1989), 471–494.

[12]

J. C. Fiorot and J. Tabka. 1991. Shape-preserving C² cubic polynomial interpolating splines. Math. Comput. 57, 195 (1991), 291–298.

[13]

F. Fritsch and R. Carlson.1980. Monotone piecewise cubic interpolation. SIAM J. Numer. Anal. 17, 2 (1980), 238–246.

Digital Library

[14]

F. N. Fritsch. 1982. Piecewise cubic Hermite interpolation package, final specifications. Computer Documentation UCID-30194, Lawrence Livermore National Laboratory (1982).

[15]

J. A. Gregory. 1985. Shape Preserving Spline Interpolation. Technical Report. NASA, Langley Research Center Computational Geometry and Computer-Aided Design.

[16]

J. A. Gregory and R. Delbourgo. 1982. Piecewise rational quadratic interpolation to monotonic data. IMA J. Numer. Anal. 2, 2 (1982), 123–130.

[17]

X. Han. 2018. Shape-preserving piecewise rational interpolation with higher order continuity. Appl. Math. Comput. 337:1–13 (2018).

[18]

R. M. Haralick and L. T. Watson. 1981. A facet model for image data. Comput. Graph. Image Process. 15 (1981), 113–129.

[19]

D. L. Herman and M. J. Oftedal. 2015. Techniques and Workflows for Computer Graphics Animation Systems. Technical Report. US Patent 9,216,351.

[20]

W. Heß and J. W. Schmidt. 1994. Positive quartic, monotone quintic C²-spline interpolation in one and two dimensions. J. Comput. Appl. Math. 55, 1 (1994), 51–67.

Digital Library

[21]

H. T. Huynh. 1993. Accurate monotone cubic interpolation. SIAM J. Numer. Anal. 30, 1 (1993), 57–100.

Digital Library

[22]

G. D. Knott. 2012. Interpolating cubic splines. Springer Sci. Bus. Media 18 (2012).

[23]

F. Leitenstorfer and G. Tutz. 2006. Generalized monotonic regression based on B-splines with an application to air pollution data. Biostatistics 8, 3 (2006), 654–673.

[24]

T. C. H. Lux. 2020. Interpolants and Error Bounds for Modeling and Predicting Variability in Computer Systems. Ph.D. Dissertation. Ph.D. thesis, Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, Virginia.

[25]

T. C. H. Lux, L. T. Watson, T. H. Chang, L. Xu, Y. Wang, and Y. Hong. 2020. An algorithm for constructing monotone quintic interpolating splines. In SCSSpring Simulation Multiconference, High Performance Computing Symposium.

[26]

C. Manni and P. Sablonnière. 1997. Monotone interpolation of order 3 by C² cubic splines. IMA J. Numer. Anal. 17, 2 (1997), 305–320.

[27]

D. F. McAllister and J. A. Roulier. 1981. Algorithm 574: Shape-preserving osculatory quadratic splines [E1, E2]. ACM Trans. Math. Softw. 7, 3 (1981), 384–386.

Digital Library

[28]

D. F. McAllister and J. A. Roulier. 1981. An algorithm for computing a shape-preserving osculatory quadratic spline. ACM Trans. Math. Softw. 7, 3 (1981), 331–347.

Digital Library

[29]

C. B. Moler. 2008. Numerical Computing with Matlab. The MathWorks Inc., Natick, Massachusetts.

[30]

B. Mulansky and M. Neamtu. 1991. On the Existence of Shape Preserving Interpolation Operators. Ph.D. Dissertation. University of Twente, Vancouver.

[31]

A. R. M. Piah and K. Unsworth. 2011. Improved sufficient conditions for monotonic piecewise rational quartic interpolation. Sains Malays. 40, 10 (2011), 1173–1178.

[32]

S. Pruess. 1993. Shape preserving C² cubic spline interpolation. IMA J. Numer. Anal. 13, 4 (1993), 493–507.

[33]

A. Quint. 2003. Scalable vector graphics. IEEE Multim. 10, 3 (2003), 99–102.

[34]

J. O. Ramsay. 1988. Monotone regression splines in action. Statist. Sci. 3, 4 (1988), 425–441.

[35]

Larry L. Schumaker. 1983. On shape preserving quadratic spline interpolation. SIAM J. Numer. Anal. 20, 4 (1983), 854–864.

Digital Library

[36]

G. Ulrich and L. T. Watson. 1990. Positivity Conditions for Quartic Polynomials. Technical Report 90-57. Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, Virginia.

Digital Library

[37]

G. Ulrich and L. T. Watson. 1994. Positivity conditions for quartic polynomials. SIAM J. Sci. Comput. 15, 3 (1994), 528–544.

Digital Library

[38]

Q. Wang and J. Tan. 2004. Rational quartic spline involving shape parameters. J. Inf. Computat. Sci. 1, 1 (2004), 127–130.

[39]

J. Yao and K. E. Nelson. 2018. An unconditionally monotone C² quartic spline method with nonoscillation derivatives. Adv. Pure Math. 8, 1 (2018), 25–40.

[40]

Y. Zhu and X. Han. 2015. C² rational quartic interpolation spline with local shape preserving property. Appl. Math. Lett. 46 (2015), 57–63.

[41]

Y. Zhu and X. Han. 2015. Shape preserving C² rational quartic interpolation spline with two parameters. Int. J. Comput. Math. 92, 10 (2015), 2160–2177.

Digital Library

Cited By

Ouermi TKirby RBerzins M(2024)Algorithm 1041: HiPPIS—A High-order Positivity-preserving Mapping Software for Structured MeshesACM Transactions on Mathematical Software10.1145/363229150:1(1-31)Online publication date: 16-Mar-2024
https://dl.acm.org/doi/10.1145/3632291
Hoof SJaeckel JThormaehlen L(2023)Axion helioscopes as solar thermometersJournal of Cosmology and Astroparticle Physics10.1088/1475-7516/2023/10/0242023:10(024)Online publication date: 6-Oct-2023
https://doi.org/10.1088/1475-7516/2023/10/024

Index Terms

Algorithm 1031: MQSI—Monotone Quintic Spline Interpolation

Recommendations

An algorithm for constructing monotone quintic interpolating splines
SpringSim '20: Proceedings of the 2020 Spring Simulation Conference

A novel algorithm for computing monotone order six piecewise polynomial interpolants is proposed. Algebraic constraints for enforcing monotonicity are provided that align with quintic monotonicity theory. The algorithm is implemented, tested, and ...
Shape-preserving, multiscale interpolation by univariate curvature-based cubic L₁ splines in cartesian and polar coordinates

We investigate C¹-smooth univariate curvature-based cubic L₁ interpolating splines in Cartesian and polar coordinates. The coefficients of these splines are calculated by minimizing the L₁ norm of curvature. We compare these curvature-based cubic L₁ ...
Shape-preserving univariate cubic and higher-degree L1 splines with function-value-based and multistep minimization principles

We investigate univariate C^2 quintic L"1 splines and C^3 seventh-degree L"1 splines and revisit C^1 cubic L"1 splines. We first investigate these L"1 splines when they are calculated by minimizing integrals of absolute values of expressions involving ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 49, Issue 1

March 2023

250 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/3587918

Editors:
Zhaojun Bai
University of California at Davis, USA
,
Wolfgang Bangerth
Colorado State University, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 March 2023

Online AM: 01 November 2022

Accepted: 14 September 2022

Revised: 25 August 2022

Received: 22 April 2021

Published in TOMS Volume 49, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
327
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)5

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ouermi TKirby RBerzins M(2024)Algorithm 1041: HiPPIS—A High-order Positivity-preserving Mapping Software for Structured MeshesACM Transactions on Mathematical Software10.1145/363229150:1(1-31)Online publication date: 16-Mar-2024
https://dl.acm.org/doi/10.1145/3632291
Hoof SJaeckel JThormaehlen L(2023)Axion helioscopes as solar thermometersJournal of Cosmology and Astroparticle Physics10.1088/1475-7516/2023/10/0242023:10(024)Online publication date: 6-Oct-2023
https://doi.org/10.1088/1475-7516/2023/10/024

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents