article

Free access

Algorithm 681: INTBIS, a portable interval Newton/bisection package

Editor: John R. Rice Authors:

R. Baker Kearfott,

Manuel Novoa, IIIAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 16, Issue 2

Pages 152 - 157

https://doi.org/10.1145/78928.78931

Published: 01 June 1990 Publication History

Abstract

We present a portable software package for finding all real roots of a system of nonlinear equations within a region defined by bounds on the variables. Where practical, the package should find all roots with mathematical certainty. Though based on interval Newton methods, it is self-contained. It allows various control and output options and does not require programming if the equations are polynomials; it is structured for further algorithmic research. Its practicality does not depend in a simple way on the dimension of the system or on the degree of nonlinearity.

Supplementary Material

INTBIS (681.gz) (681.gz)

interval Newton/bisection methods: real roots of a system of nonlinear equations within a region defined by bounds on the variables Gams: F2

Download
56.52 KB

References

[1]

ALEFELD, G., AND HERZBERGER, J. Introduction to Interval Computations. Academic Press, New York, 1983.

[2]

DONGARRA, J. J., MOLER, C. B., BUNCH, J. R., AND STEWART, G.W. LINPACK Users' Guide. SIAM, Philadelphia, 1979.

[3]

DONGARRA, J. J., AND GROSSE, E. Distribution of mathematical software via electronic mail. ACM SIGNUM Newsl. 20, 3 (July 1985), 45-47.

[4]

HANSEN, E. R., AND GREENBERG, R.i. An Interval Newton method. Appl. Math. Comput. 12 (1983), 89-98.

[5]

HANSEN, E. a., AND SENGUPTA, S. Bounding solutions of systems of equations using interval analysis. BIT 21 {1981), 203-211.

[6]

KEARFOTT, R.S. Abstract generalized bisection and a cost bound. Math. Comput. 49, 179 (July 1987), 187-202.

[7]

KEARFOTT, R.B. Some tests of generalized bisection. ACM Trans. Math. Softw. 13, 3 (Sept. 1987).

[8]

KEARFOTT, R.B. On handling singular systems with interval Newton methods. In Proceedings of the Twelfth IMACS World Congress on Scientific Computation, 1988.

[9]

KEARFOTT, R.B. Preconditioners for the interval Gauss-Seidel method. SIAM J. Numer. Anal. 27, 3 (June 1990).

[10]

KEARFOTT, R.S. Interval arithmetic methods for nonlinear systems and nonlinear optimization: An introductory review. In Impacts of Recent Computer Advances on Operations Research. Elsevier, New York, 1989.

[11]

MOORE, R. E., AND JONES, S.T. Safe starting regions for iterative methods. SIAM J. Numer. Anal. 14, 6 (Dec. 1977), 1051-1065.

[12]

MOORE, R.E. Methods and Applications of Interval Analysis. SIAM, Philadelphia, 1979.

[13]

MOORE, R. E., ED. Reliability in Computing. Academic Press, New York, 1988.

[14]

MORGAN, A.P. Solving Polynomial Systems using Continuation for Engineering and Scientific Problems. Prentice-Hall, Englewood Cliffs, N.J., 1987.

[15]

RATSCHEK, H., AND ROKNE, J.G. Computer Methods for the Range of Functions. Horwood, Chichester, England, 1984.

Cited By

Vanaret C(2024)Interval constraint programming for globally solving catalog-based categorical optimizationJournal of Global Optimization10.1007/s10898-023-01362-089:2(457-476)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10898-023-01362-0
Fernández JG.-Tóth B(2022)Interval Tools in Branch-and-Bound Methods for Global OptimizationThe Palgrave Handbook of Operations Research10.1007/978-3-030-96935-6_8(237-267)Online publication date: 8-Jul-2022
https://doi.org/10.1007/978-3-030-96935-6_8
Paulsen BWang JWang CRothermel GBae D(2020)ReluDiffProceedings of the ACM/IEEE 42nd International Conference on Software Engineering10.1145/3377811.3380337(714-726)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377811.3380337
Show More Cited By

Index Terms

Algorithm 681: INTBIS, a portable interval Newton/bisection package
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Nonlinear equations
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

REDUCE package for the indefinite and definite summation

This article describes the REDUCE package ZEILBERG implemented by Gregor Stölting and the author which can be obtained from RedLib, accessible via anonymous ftp on ftp.zib-berlin.de in the directory pub/redlib/rules.The REDUCE package ZEILBERG is a ...
A MACSYMA package for the generation and manipulation of chebyshev series
ISSAC '89: Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation

Techniques for a MACSYMA package for expanding an arbitrary univariate expression as a truncated series in Chebyshev polynomials and manipulating such expansions is described. A data structure is introduced to represent a truncated expansion in a set of ...
Algorithm 757: MISCFUN, a software package to compute uncommon special functions

MISCFUN (MISCellaneous FUNctions) is a Fortran package for the evaluation of several special functions, which are not used often enough to have been included in the standard libraries or packages. The package uses Chebyshev expansions as the underlying ...

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 16, Issue 2

June 1990

70 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/78928

Editor:
John R. Rice

Issue’s Table of Contents

Copyright © 1990 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1990

Published in TOMS Volume 16, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

122
Total Citations
View Citations
1,256
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)13

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Vanaret C(2024)Interval constraint programming for globally solving catalog-based categorical optimizationJournal of Global Optimization10.1007/s10898-023-01362-089:2(457-476)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10898-023-01362-0
Fernández JG.-Tóth B(2022)Interval Tools in Branch-and-Bound Methods for Global OptimizationThe Palgrave Handbook of Operations Research10.1007/978-3-030-96935-6_8(237-267)Online publication date: 8-Jul-2022
https://doi.org/10.1007/978-3-030-96935-6_8
Paulsen BWang JWang CRothermel GBae D(2020)ReluDiffProceedings of the ACM/IEEE 42nd International Conference on Software Engineering10.1145/3377811.3380337(714-726)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377811.3380337
Pickard JCarretero JMerlet J(2020)Appropriate synthesis of the four-bar linkageMechanism and Machine Theory10.1016/j.mechmachtheory.2020.103965153(103965)Online publication date: Nov-2020
https://doi.org/10.1016/j.mechmachtheory.2020.103965
Pickard JCarretero JMerlet J(2019)Appropriate analysis of the four-bar linkageMechanism and Machine Theory10.1016/j.mechmachtheory.2019.04.013139(237-250)Online publication date: Sep-2019
https://doi.org/10.1016/j.mechmachtheory.2019.04.013
Huang CKong SGao SZufferey D(2019)Evaluating Branching Heuristics in Interval Constraint Propagation for SatisfiabilityNumerical Software Verification10.1007/978-3-030-28423-7_6(85-100)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-28423-7_6
Araya INeveu B(2018)lsmearJournal of Global Optimization10.1007/s10898-017-0569-y71:3(483-500)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s10898-017-0569-y
Henderson NRêgo MImbiriba J(2017)Topographical global initialization for finding all solutions of nonlinear systems with constraintsApplied Numerical Mathematics10.1016/j.apnum.2016.10.007112(155-166)Online publication date: Feb-2017
https://doi.org/10.1016/j.apnum.2016.10.007
Sans OColetta RTrombettoni G(2016)An Interval Filtering Operator for Upper and Lower Bounding in Constrained Global Optimization2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI.2016.0042(218-225)Online publication date: Nov-2016
https://doi.org/10.1109/ICTAI.2016.0042
Araya IReyes V(2016)Interval Branch-and-Bound algorithms for optimization and constraint satisfactionJournal of Global Optimization10.1007/s10898-015-0390-465:4(837-866)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s10898-015-0390-4
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Issue’s Table of Contents