@InProceedings{Bujnak-Kukelova-Pajdla-CVPR-2012, IS = { zkontrolovano 14 Jan 2013 }, UPDATE = { 2012-10-10 }, author = {Bujnak, Martin and Kukelova, Zuzana and Pajdla, Tom{\'a}{\v s}}, title = {Making Minimal Solvers Fast}, booktitle = {CVPR 2012: Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition}, year = {2012}, pages = {1506-1513}, publisher = {IEEE Computer Society Press}, address = {New York, USA}, month = {June}, organization = {IEEE Computer Society}, annote = {In this paper we propose methods for speeding up minimal solvers based on Gr\"{o}bner bases and action matrix eigenvalue computations. Almost all existing Gr\"{o}bner basis solvers spend most time in the eigenvalue computation. We present two methods which speed up this phase of Gr\"{o}bner basis solvers: (1) a method based on a modified FGLM algorithm for transforming Gr\"{o}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 many existing solvers. We demonstrate them on three important minimal computer vision problems.}, authorship = {34-33-33}, book_pages = {3696}, day = {16-21}, doi = {10.1109/CVPR.2012.6247853}, isbn = {978-1-4673-1228-8}, issn = {1063-6919}, keywords = {Minimal problems, Gr\"{o}bner basis}, prestige = {important}, project = {FP7-SPACE-218814 PRoVisG, FP7-SPACE-241523 PRoViScout, SGS12/191/OHK3/3T/13}, psurl = {[10.1109/CVPR.2012.6247840.pdf]}, venue = {Providence, USA}, ut_isi = {000309166201083}, }