Real root finding for low rank linear matrices

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00340150" target="_blank" >RIV/68407700:21230/20:00340150 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s00200-019-00396-w" target="_blank" >https://doi.org/10.1007/s00200-019-00396-w</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00200-019-00396-w" target="_blank" >10.1007/s00200-019-00396-w</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Real root finding for low rank linear matrices

Popis výsledku v původním jazyce

We consider mx s matrices (with m>= s) in a real affine subspace of dimension n. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite set of points that intersects each connected component of the low rank real algebraic set. The complexity of our algorithm is studied thoroughly. It is polynomial in (n+m(s-r)n). It improves on the state-of-the-art in computer algebra and effective real algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach.

Název v anglickém jazyce

Real root finding for low rank linear matrices

Popis výsledku anglicky

We consider mx s matrices (with m>= s) in a real affine subspace of dimension n. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite set of points that intersects each connected component of the low rank real algebraic set. The complexity of our algorithm is studied thoroughly. It is polynomial in (n+m(s-r)n). It improves on the state-of-the-art in computer algebra and effective real algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10100 - Mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Applicable Algebra in Engineering, Communication and Computing

ISSN

0938-1279

e-ISSN

1432-0622

Svazek periodika

31

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

33

Strana od-do

101-133

Kód UT WoS článku

000518201000002

EID výsledku v databázi Scopus

2-s2.0-85069658735