View in EDS

Real root finding for determinants of linear matrices.

Saved in:
Bibliographic Details
Title: Real root finding for determinants of linear matrices.
Authors: Henrion, Didier1,2,3 henrion@laas.fr, Naldi, Simone1,2 snaldi@laas.fr, Safey El Din, Mohab4,5,6,7 Mohab.Safey@lip6.fr
Source: Journal of Symbolic Computation. May2016, Vol. 74, p205-238. 34p.
Subjects: Determinants (Mathematics), Matrices (Mathematics), Coefficients (Statistics), Mathematical connectedness, Control theory (Engineering), Computational geometry, Mathematical optimization
Abstract: Let A 0 , A 1 , … , A n be given square matrices of size m with rational coefficients. The paper focuses on the exact computation of one point in each connected component of the real determinantal variety { x ∈ R n : det ⁡ ( A 0 + x 1 A 1 + ⋯ + x n A n ) = 0 } . Such a problem finds applications in many areas such as control theory, computational geometry, optimization, etc. Under some genericity assumptions on the coefficients of the matrices, we provide an algorithm solving this problem whose runtime is essentially polynomial in the binomial coefficient ( n + m n ) . We also report on experiments with a computer implementation of this algorithm. Its practical performance illustrates the complexity estimates. In particular, we emphasize that for subfamilies of this problem where m is fixed, the complexity is polynomial in n . [ABSTRACT FROM AUTHOR]
Copyright of Journal of Symbolic Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 111012091
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Real root finding for determinants of linear matrices.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Henrion%2C+Didier%22">Henrion, Didier</searchLink><relatesTo>1,2,3</relatesTo><i> henrion@laas.fr</i><br /><searchLink fieldCode="AR" term="%22Naldi%2C+Simone%22">Naldi, Simone</searchLink><relatesTo>1,2</relatesTo><i> snaldi@laas.fr</i><br /><searchLink fieldCode="AR" term="%22Safey+El+Din%2C+Mohab%22">Safey El Din, Mohab</searchLink><relatesTo>4,5,6,7</relatesTo><i> Mohab.Safey@lip6.fr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Symbolic+Computation%22">Journal of Symbolic Computation</searchLink>. May2016, Vol. 74, p205-238. 34p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Determinants+%28Mathematics%29%22">Determinants (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Matrices+%28Mathematics%29%22">Matrices (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Coefficients+%28Statistics%29%22">Coefficients (Statistics)</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+connectedness%22">Mathematical connectedness</searchLink><br /><searchLink fieldCode="DE" term="%22Control+theory+%28Engineering%29%22">Control theory (Engineering)</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Let A 0 , A 1 , … , A n be given square matrices of size m with rational coefficients. The paper focuses on the exact computation of one point in each connected component of the real determinantal variety { x ∈ R n : det ⁡ ( A 0 + x 1 A 1 + ⋯ + x n A n ) = 0 } . Such a problem finds applications in many areas such as control theory, computational geometry, optimization, etc. Under some genericity assumptions on the coefficients of the matrices, we provide an algorithm solving this problem whose runtime is essentially polynomial in the binomial coefficient ( n + m n ) . We also report on experiments with a computer implementation of this algorithm. Its practical performance illustrates the complexity estimates. In particular, we emphasize that for subfamilies of this problem where m is fixed, the complexity is polynomial in n . [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Symbolic Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=111012091
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.jsc.2015.06.010
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 34
        StartPage: 205
    Subjects:
      – SubjectFull: Determinants (Mathematics)
        Type: general
      – SubjectFull: Matrices (Mathematics)
        Type: general
      – SubjectFull: Coefficients (Statistics)
        Type: general
      – SubjectFull: Mathematical connectedness
        Type: general
      – SubjectFull: Control theory (Engineering)
        Type: general
      – SubjectFull: Computational geometry
        Type: general
      – SubjectFull: Mathematical optimization
        Type: general
    Titles:
      – TitleFull: Real root finding for determinants of linear matrices.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Henrion, Didier
      – PersonEntity:
          Name:
            NameFull: Naldi, Simone
      – PersonEntity:
          Name:
            NameFull: Safey El Din, Mohab
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 05
              Text: May2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 07477171
          Numbering:
            – Type: volume
              Value: 74
          Titles:
            – TitleFull: Journal of Symbolic Computation
              Type: main
ResultId 1