Making Minimal Solvers Fast
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F12%3A00200360" target="_blank" >RIV/68407700:21230/12:00200360 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1109/CVPR.2012.6247853" target="_blank" >http://dx.doi.org/10.1109/CVPR.2012.6247853</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/CVPR.2012.6247853" target="_blank" >10.1109/CVPR.2012.6247853</a>
Alternative languages
Result language
angličtina
Original language name
Making Minimal Solvers Fast
Original language description
In this paper we propose methods for speeding up minimal solvers based on Gröbner bases and action matrix eigenvalue computations. Almost all existing Gröbner basis solvers spend most time in the eigenvalue computation. We present two methods which speedup this phase of Gröbner basis solvers: (1) a method based on a modified FGLM algorithm for transforming Gröbner bases which results in a single-variable polynomial followed by direct calculation of its roots using Sturm-sequences and, for larger problems, (2) fast calculation of the characteristic polynomial of an action matrix, again solved using Sturm-sequences. We enhanced the FGLM method by replacing time consuming polynomial division performed in standard FGLM algorithm with efficient matrix-vector multiplication and we show how this method is related to the characteristic polynomial method. Our approaches allow computing roots only in some feasible interval and in desired precision. Proposed methods can significantly speedup man
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
JD - Use of computers, robotics and its application
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
CVPR 2012: Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition
ISBN
978-1-4673-1228-8
ISSN
1063-6919
e-ISSN
—
Number of pages
8
Pages from-to
1506-1513
Publisher name
IEEE Computer Society Press
Place of publication
New York
Event location
Providence, Rhode Island
Event date
Jun 16, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000309166201083