[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2930889.2930916acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
research-article

Determinantal Sets, Singularities and Application to Optimal Control in Medical Imagery

Published: 20 July 2016 Publication History

Abstract

Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast between two biological matters on the pictures.
Geometric optimal control leads us here to analyze meromorphic vector fields depending upon physical parameters, and having their singularities defined by a determinantal variety. The involved matrix has polynomial entries with respect to both the state variables and the parameters. Taking into account the physical constraints of the problem, one needs to classify, with respect to the parameters, the number of real singularities lying in some prescribed semi-algebraic set.
We develop a dedicated algorithm for real root classification of the singularities of the rank defects of a polynomial matrix, cut with a given semi-algebraic set. The algorithm works under some genericity assumptions which are easy to check. These assumptions are not so restrictive and are satisfied in the aforementioned application. As more general strategies for real root classification do, our algorithm needs to compute the critical loci of some maps, intersections with the boundary of the semi-algebraic domain, etc. In order to compute these objects, the determinantal structure is exploited through a stratification by the rank of the polynomial matrix. This speeds up the computations by a factor 100. Furthermore, our implementation is able to solve the application in medical imagery, which was out of reach of more general algorithms for real root classification. For instance, computational results show that the contrast problem where one of the matters is water is partitioned into three distinct classes.

References

[1]
J. Bochnak, M. Coste, and M.-F. Roy. Real algebraic geometry, volume 36 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) {Results in Mathematics and Related Areas (3)}. Springer-Verlag, Berlin, 1998. Translated from the 1987 French original, Revised by the authors.
[2]
B. Bonnard, M. Chyba, A. Jacquemard, and J. Marriott. Algebraic geometric classification of the singular flow in the contrast imaging problem in nuclear magnetic resonance. Math. Control Relat. Fields, 3(4):397--432, 2013.
[3]
B. Bonnard, O. Cots, S.J. Glaser, M. Lapert, D. Sugny, and Y. Zhang. Geometric optimal control of the contrast imaging problem in nuclear magnetic resonance. IEEE Trans. Automat. Control, 57(8):1957--1969, 2012.
[4]
C. W. Brown and J. H. Davenport. The complexity of quantifier elimination and cylindrical algebraic decomposition. In ISSAC 2007, pages 54--60. ACM, New York, 2007.
[5]
W. Bruns and U. Vetter. Determinantal Rings. Springer, 2014.
[6]
M. Chyba, J-M. Coron, P. Gabriel, A. Jacquemard, G. Patterson, G. Picot, and P. Shang. Optimal geometric control applied to the protein misfolding cyclic amplification process. Acta Applicandae Mathematicae, 135(1):145--173, 2015.
[7]
G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975), pages 134--183. Lecture Notes in Comput. Sci., Vol. 33. Springer, Berlin, 1975.
[8]
M. Coste and M. Shiota. Thom's first isotopy lemma: a semialgebraic version, with uniform bound. In Real analytic and algebraic geometry (Trento, 1992), pages 83--101. de Gruyter, Berlin, 1995.
[9]
J. H. Davenport and J. Heintz. Real quantifier elimination is doubly exponential. J. Symbolic Comput., 5(1--2):29--35, 1988.
[10]
M. Demazure. Bifurcations and catastrophes. Universitext. Springer-Verlag, Berlin, 2000. Geometry of solutions to nonlinear problems, Translated from the 1989 French original by D. Chillingworth.
[11]
J.-C. Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F_5). In Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pages 75--83 (electronic), New York, 2002. ACM.
[12]
J.-C. Faugère. FGb: A Library for Computing Gröbner Bases. In Komei Fukuda, Joris Hoeven, Michael Joswig, and Nobuki Takayama, editors, Mathematical Software - ICMS 2010, volume 6327 of Lecture Notes in Computer Science, pages 84--87, Berlin, Heidelberg, September 2010. Springer Berlin / Heidelberg.
[13]
J.-C. Faugère, M. Safey El Din, and P.-J. Spaenlehauer. Critical points and Gröbner bases: the unmixed case. In Proceedings of the 2012 International Symposium on Symbolic and Algebraic Computation (ISSAC 2012), pages 162--169, 2012.
[14]
J.-C. Faugère, M. Safey El Din, and P.-J. Spaenlehauer. On the complexity of the Generalized MinRank Problem. Journal of Symbolic Computation, 55:30--58, 2013.
[15]
D. Henrion, S. Naldi, and M. Safey El Din. Exact algorithms for linear matrix inequalities. Submitted., August 2015.
[16]
D. Henrion, S. Naldi, and M. Safey El Din. Real root finding for low rank linear matrices. Submitted., June 2015.
[17]
D. Henrion, S. Naldi, and M. Safey El Din. Real root finding for rank defects in linear Hankel matrices. In Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, page 26p., Bath, United Kingdom, July 2015.
[18]
D. Henrion, S. Naldi, and M. Safey El Din. Real root finding for determinants of linear matrices. Journal of Symbolic Computation, 74:205 -- 238, 2016.
[19]
H. Hong and M. Safey El Din. Variant quantifier elimination. Journal of Symbolic Computation, 47(7):883 -- 901, 2012. International Symposium on Symbolic and Algebraic Computation (ISSAC 2009).
[20]
D. Lazard and F. Rouillier. Solving parametric polynomial systems. Journal of Symbolic Computation, 42(6):636--667, 2007.
[21]
F. Lemaire, M. Moreno Maza, and Y. Xie. The regularchains library. In Maple conference, volume 5, pages 355--368, 2005.
[22]
S. McCallum. On projection in CAD-based quantifier elimination with equational constraint. In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (Vancouver, BC), pages 145--149 (electronic). ACM, New York, 1999.
[23]
L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze, and E. F. Mishchenko. The mathematical theory of optimal processes. Translated from the Russian by K. N. Trirogoff; edited by L. W. Neustadt. Interscience Publishers John Wiley & Sons, Inc., New York-London, 1962.
[24]
J. I. Rodriguez and X. Tang. Data-discriminants of likelihood equations. In Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '15, pages 307--314, New York, NY, USA, 2015. ACM.
[25]
P.-J. Spaenlehauer. On the complexity of computing critical points with Gröbner bases. SIAM Journal on Optimization, 24(3):1382--1401, 2014.
[26]
L. Yang, X. Hou, and B. Xia. A complete algorithm for automated discovering of a class of inequality-type theorems. Sci. China Ser. F, 44(1):33--49, 2001.

Cited By

View all
  • (2024)Solving parameter-dependent semi-algebraic systemsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669718(447-456)Online publication date: 16-Jul-2024
  • (2020)Real root finding for low rank linear matricesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-019-00396-w31:2(101-133)Online publication date: 1-Mar-2020
  • (2020)Classification of Hyperbolic Singularities in Interval 3-Dimensional Linear Differential SystemsInformation Processing and Management of Uncertainty in Knowledge-Based Systems10.1007/978-3-030-50143-3_2(13-27)Online publication date: 5-Jun-2020
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ISSAC '16: Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation
July 2016
434 pages
ISBN:9781450343800
DOI:10.1145/2930889
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2016

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. applications
  2. polynomial system solving
  3. real geometry

Qualifiers

  • Research-article

Funding Sources

  • Institut universitaire de France
  • ANR-DFG program Explosys

Conference

ISSAC '16
Sponsor:

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 31 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Solving parameter-dependent semi-algebraic systemsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669718(447-456)Online publication date: 16-Jul-2024
  • (2020)Real root finding for low rank linear matricesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-019-00396-w31:2(101-133)Online publication date: 1-Mar-2020
  • (2020)Classification of Hyperbolic Singularities in Interval 3-Dimensional Linear Differential SystemsInformation Processing and Management of Uncertainty in Knowledge-Based Systems10.1007/978-3-030-50143-3_2(13-27)Online publication date: 5-Jun-2020
  • (2018)Real Root Finding for Equivariant Semi-algebraic SystemsProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209023(335-342)Online publication date: 11-Jul-2018

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media