Article

Free access

Efficient algorithms for computing the nearest polynomial with constrained roots

Authors:

Markus A. Hitz,

Erich KaltofenAuthors Info & Claims

ISSAC '98: Proceedings of the 1998 international symposium on Symbolic and algebraic computation

Pages 236 - 243

https://doi.org/10.1145/281508.281624

Published: 01 August 1998 Publication History

PDF eReader

References

[1]

BARMISH, B. R., AND KANG, H. I. A survey of extreme point results for robustness of control systems. Automatica 29, 1 (1993), 13-35.

Digital Library

Google Scholar

[2]

CHEN, J., FAN, K. H., AND NETT, C. N. Structured singular values and stability analysis of uncertain polynomials, part 1: the generalized #. Systems ~ Control Letters 23, 1 (1994), 53-65.

Digital Library

Google Scholar

[3]

CHEN, J., FAN, K. H., AND NETT~ C. N. Structured singular values and stability analysis of uncertain polynomials, part 1: a missing link. Systems ~ Control Letters 23, 2 (1994), 97-109.

Digital Library

Google Scholar

[4]

COLEMAN, T. F., AND LI, Y. A global and quadratically convergent method for linear 1~ problems. SIAM J. Numer. Anal. 29, 4 (1992), 1166-1186.

Digital Library

Google Scholar

[5]

DESAGES, A. C., CASTRO, L., AND H., C. Distance of a complex coefficient stable polynomial from the boundary of the stability set. Multidimensional Systerns and Signal Processing 2 (1991), 189-210.

Digital Library

Google Scholar

[6]

ECKER~ J. (~.~ AND KUPFERSCHMID~ M. Introduction to Operations Research. John Wiley & Sons, New York, N.Y., 1988.

Google Scholar

[7]

GANTMACHER, F. R. Matriz Theory. Chelsea Publishing Company, New York, N.Y., 1959.

Google Scholar

[8]

GOLUB, G. H., AND VAN LOAN, C. F. Matriz Computations, 1~t ed. The John Hopkins University Press, Baltimore, M.D., 1983.

Google Scholar

[9]

HITZ, M. A. Efficient Algorithms for Computing the Nearest Polynomial with Constrained Roots. PhD thesis, Rensselaer Polytechnic Institute, Troy, N.Y., 1998.

Digital Library

Google Scholar

[10]

JOYA, K., AND FURUTA, K. Criteria for Schur and ~-stability of a family of polynomials constrained with /P-norm. In Proc. IEEE Conf. Dec. and Control (1991), pp. 433-434.

Google Scholar

[11]

KARMARKAR, N., AND LAKSHMAN, Y. N. Approximate polynomial greatest common divisors and nearest singular polynomials. In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC'96 (1996), pp. 35-39.

Digital Library

Google Scholar

[12]

KARMARKAR, N., AND LAKSHMAN, Y. N. On approximate GCDs of univariate polynomials. Submitted for publication (1997).

Google Scholar

[13]

KHARITONOV~ V. L. Asymptotic stability of an equilibrium position of a family of systems of linear differential equations. Differensial'nye Uravnenya 14, 11 (1978), 2086-2088.

Google Scholar

[14]

KHARITONOV, V. L. On 3o generalization of a stability criterion. Akademii hank Kazakhskoi SSR, Seria fizikomathematicheskaia 1 (1978), 53-57.

Google Scholar

[15]

KHARITONOV~ V. L. Asymptotic stability of an equilibrium position of a family of systems of linear differential equations. Differential Equations 14 (1979), 1483-1485.

Google Scholar

[16]

KOGAN, J. How near is a stable polynomial to an unstable polynomial? IEEE Trans. Circuits Syst. I CAS-39, 8 (1992), 676-680.

Crossref

Google Scholar

[17]

KREIN, ~/{. G., AND NAIMARK, ~/{. A. The method of symmetric and Hermitian forms in the theory of the separation of the roots of algebraic equations. Linear and Multilinear Algebra 10 (1981), 265-308. Originally published in Russian, Kharkov (1936).

Crossref

Google Scholar

[18]

MARDEN, M. Geometry of Polynomials, 2~d ed. Mathematical Surveys, Number 3. American Mathematical Society, Providence, R.I., 1966.

Google Scholar

[19]

P~REZ, F., ABDALLAH, C., AND D., D. Robustness analysis of polynomials with linearly correlated uncertain coefficients in /P-normed balls. In Proc. IEEE Conf. Dec. and Control (1994), pp. 2996-2997.

Google Scholar

[20]

QIu, L., AND DAVISON, E. J. A simple procedure for the exact stability robustness computation of polynomials with affine coefficient perturbations. Systems and Control Letters 13 (1989), 413-420.

Digital Library

Google Scholar

[21]

RANTZER~ A. Stability conditions for polytopes of polynomials. IEEE Trans. Auto. Control AC-37, 1 (1992), 79-89.

Crossref

Google Scholar

[22]

STIEFEL~ E. /Jber diskrete und lineare Tschebyscheff- Approximationen. Numerische Mathematik 1 (1959), 1-28.

Digital Library

Google Scholar

[23]

STIEFEL~ E. Note on Jordan elimination, linear programming and Tschebyscheff approximation. Numerische Mathematik 2 (1960), 1-17.

Digital Library

Google Scholar

[24]

TEMPO~ R. A simple test for Schur stability of a diamond of complex polynomials. In Proc. IEEE Conf. Dec. and Control (1989), pp. 1892-1895.

Crossref

Google Scholar

[25]

TSYPKIN, Y. Z., AND POLYAK, B. T. Frequency domain criteria for/P-robust stability of continuous linear systems. IEEE Trans. Auto. Control AC-36 (1991), 1464-1469.

Crossref

Google Scholar

Cited By

View all

Hu WHuang HZhang RHuang JYi Y(2024)A new algorithm for computing the nearest polynomial to multiple given polynomials via weighted ℓ2,-norm minimization and its complex extensionTheoretical Computer Science10.1016/j.tcs.2024.114594(114594)Online publication date: Apr-2024
https://doi.org/10.1016/j.tcs.2024.114594
Mohammadi AMalik HAbbaszadeh M(2023)Vehicle Lateral Motion Dynamics Under Braking/ABS Cyber-Physical AttacksIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.329342418(4100-4115)Online publication date: 2023
https://doi.org/10.1109/TIFS.2023.3293424
Corless RRafiee Sevyeri L(2020)Approximate GCD in a Bernstein BasisMaple in Mathematics Education and Research10.1007/978-3-030-41258-6_6(77-91)Online publication date: 28-Feb-2020
https://doi.org/10.1007/978-3-030-41258-6_6
Show More Cited By

Index Terms

Efficient algorithms for computing the nearest polynomial with constrained roots
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials

Recommendations

Efficient algorithms for computing the nearest polynomial with constrained roots
A Matlab package computing polynomial roots and multiplicities

MULTROOT is a collection of Matlab modules for accurate computation of polynomial roots, especially roots with high multiplicities, using standard machine precision. As a blackbox-type software, MULTROOT requires the polynomial coefficients as the only ...
Efficient isolation of polynomial's real roots
Special issue: Proceedings of the international conference on linear algebra and arithmetic, Rabat, Morocco, 28-31 May 2001

This paper revisits an algorithm isolating the real roots of a univariate polynomial using Descartes' rule of signs. It follows work of Vincent, Uspensky, Collins and Akritas, Johnson, Krandick.Our first contribution is a generic algorithm which enables ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '98: Proceedings of the 1998 international symposium on Symbolic and algebraic computation

August 1998

330 pages

ISBN:1581130023

DOI:10.1145/281508

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: 01 August 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC98

Sponsor:

German Comp Soc
SIGNUM
SIGSAM

ISSAC98: International Symposium on Symbolic and Algebraic Computation

August 13 - 15, 1998

Rostock, Germany

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
423
Total Downloads

Downloads (Last 12 months)132
Downloads (Last 6 weeks)46

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hu WHuang HZhang RHuang JYi Y(2024)A new algorithm for computing the nearest polynomial to multiple given polynomials via weighted ℓ2,-norm minimization and its complex extensionTheoretical Computer Science10.1016/j.tcs.2024.114594(114594)Online publication date: Apr-2024
https://doi.org/10.1016/j.tcs.2024.114594
Mohammadi AMalik HAbbaszadeh M(2023)Vehicle Lateral Motion Dynamics Under Braking/ABS Cyber-Physical AttacksIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.329342418(4100-4115)Online publication date: 2023
https://doi.org/10.1109/TIFS.2023.3293424
Corless RRafiee Sevyeri L(2020)Approximate GCD in a Bernstein BasisMaple in Mathematics Education and Research10.1007/978-3-030-41258-6_6(77-91)Online publication date: 28-Feb-2020
https://doi.org/10.1007/978-3-030-41258-6_6
Hu WLuo XLuo Z(2015)A unified approach to computing the nearest complex polynomial with a given zeroTheoretical Computer Science10.1016/j.tcs.2015.06.015595:C(65-81)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.06.015
Ruatta OSciabica MSzanto A(2015)Overdetermined Weierstrass iteration and the nearest consistent systemTheoretical Computer Science10.1016/j.tcs.2014.10.008562:C(346-364)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.10.008
Sekigawa HZhi LWatt S(2014)The nearest polynomial to multiple given polynomials with a given zeroProceedings of the 2014 Symposium on Symbolic-Numeric Computation10.1145/2631948.2631975(144-145)Online publication date: 28-Jul-2014
https://dl.acm.org/doi/10.1145/2631948.2631975
Rezvani NCorless RKotsireas I(2012)Using weighted norms to find nearest polynomials satisfying linear constraintsProceedings of the 2011 International Workshop on Symbolic-Numeric Computation10.1145/2331684.2331697(81-87)Online publication date: 7-Jun-2012
https://dl.acm.org/doi/10.1145/2331684.2331697
Luo ZHu WSheen D(2011)The nearest complex polynomial with a zero in a given complex domainTheoretical Computer Science10.1016/j.tcs.2011.09.016412:50(7029-7043)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1016/j.tcs.2011.09.016
Sekigawa H(2011)Computing the nearest polynomial with a zero in a given domain by using piecewise rational functionsJournal of Symbolic Computation10.1016/j.jsc.2011.08.01246:12(1318-1335)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.jsc.2011.08.012
Hutton SKaltofen EZhi LKoepf W(2010)Computing the radius of positive semidefiniteness of a multivariate real polynomial via a dual of Seidenberg's methodProceedings of the 2010 International Symposium on Symbolic and Algebraic Computation10.1145/1837934.1837979(227-234)Online publication date: 25-Jul-2010
https://dl.acm.org/doi/10.1145/1837934.1837979
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Efficient algorithms for computing the nearest polynomial with constrained roots

A Matlab package computing polynomial roots and multiplicities

Efficient isolation of polynomial's real roots