About: Making Minimal Solvers Fast

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Making Minimal Solvers Fast Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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 speed up 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 many existing solvers. We demonstrate them on three important minimal computer vision problems. 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 speed up 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 many existing solvers. We demonstrate them on three important minimal computer vision problems. (en)
Title	Making Minimal Solvers Fast Making Minimal Solvers Fast (en)
skos:prefLabel	Making Minimal Solvers Fast Making Minimal Solvers Fast (en)
skos:notation	RIV/68407700:21230/12:00200360!RIV13-MSM-21230___
http://linked.open...avai/predkladatel	Fakulta elektrotechnická
http://linked.open...avai/riv/aktivita	P S
http://linked.open...avai/riv/aktivity	P(7E09062), P(7E10046), S
http://linked.open...vai/riv/dodaniDat	2013
http://linked.open...aciTvurceVysledku	Pajdla, Tomáš Bujňák, Martin Kúkelová, Zuzana
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	České vysoké učení technické v Praze / Fakulta elektrotechnická
http://linked.open...dnocenehoVysledku	147867
http://linked.open...ai/riv/idVysledku	RIV/68407700:21230/12:00200360
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Minimal problems; Gröbner basis (en)
http://linked.open.../riv/klicoveSlovo	Gröbner basis Minimal problems
http://linked.open...ontrolniKodProRIV	[712A1FA6D4D5]
http://linked.open...v/mistoKonaniAkce	Providence, Rhode Island
http://linked.open...i/riv/mistoVydani	New York
http://linked.open...i/riv/nazevZdroje	CVPR 2012: Proceedings of the 2012 IEEE Computer Society Conference on Computer Vision and Pattern Recognition
http://linked.open...in/vavai/riv/obor	JD
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Planetary Robotics Vision Ground Processing Planetary Robotics Vision Scout
http://linked.open...UplatneniVysledku	2012
http://linked.open...iv/tvurceVysledku	Bujňák, Martin Kúkelová, Zuzana Pajdla, Tomáš
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open...ain/vavai/riv/wos	000309166201083
http://linked.open.../riv/zahajeniAkce	2012-06-16 (xsd:date)
issn	1063-6919
number of pages	8 (xsd:int)
http://bibframe.org/vocab/doi	10.1109/CVPR.2012.6247853
http://purl.org/ne...btex#hasPublisher	IEEE Computer Society Press
https://schema.org/isbn	978-1-4673-1228-8
http://localhost/t...ganizacniJednotka	21230
is http://linked.open...avai/riv/vysledek of	Making Minimal Solvers Fast

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software