Making Minimal Solvers Fast

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Making Minimal Solvers Fast

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Making Minimal Solvers Fast

Popis výsledku anglicky

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

Druh

D - Stať ve sborníku

CEP obor

JD - Využití počítačů, robotika a její aplikace

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2012

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 statě ve sborníku

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

—

Počet stran výsledku

8

Strana od-do

1506-1513

Název nakladatele

IEEE Computer Society Press

Místo vydání

New York

Místo konání akce

Providence, Rhode Island

Datum konání akce

16. 6. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000309166201083