Exploiting p-Fold Symmetries for Faster Polynomial Equation Solving

Erik Ask; Yubin Kuang; Karl Åström

Exploiting p-Fold Symmetries for Faster Polynomial Equation Solving

Erik Ask, Yubin Kuang, Karl Åström

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

Abstract

Numerous geometric problems in computer vision in-
volve the solution of systems of polynomial equations.
This is true for problems with minimal information, but
also for finding stationary points for overdetermined
problems. The state-of-the-art is based on the use of
numerical linear algebra on the large but sparse co-
efficient matrix that represents the expanded original
equation set. In this paper we present two simplifica-
tions that can be used (i) if the zero vector is one of
the solutions or (ii) if the equations display certain p-
fold symmetries. We evaluate the simplifications on a
few example problems and demonstrate that significant
speed increases are possible without loosing accuracy.

Original language	English
Title of host publication	21st International Conference on Pattern Recognition (ICPR 2012), Proceedings of
Publisher	IEEE - Institute of Electrical and Electronics Engineers Inc.
Pages	3232-3235
Number of pages	4
ISBN (Print)	978-4-9906441-1-6
Publication status	Published - 2012
Event	21st International Conference on Pattern Recognition (ICPR 2012) - Tsukuba, Japan Duration: 2012 Nov 11 → 2012 Nov 15

Conference

Conference	21st International Conference on Pattern Recognition (ICPR 2012)
Country/Territory	Japan
City	Tsukuba
Period	2012/11/11 → 2012/11/15

Bibliographical note

The proceedings of ICPR 2012 will in the future be available at IEEE Xplore. The page reference given above refer to the proceedings published on USB by IEEE, and distributed to the participants during the conference.

Subject classification (UKÄ)

Mathematical Sciences

Free keywords

geometry
algebra
computer vision
Polynomial equation solving

Cite this

@inproceedings{45645dfbc67c4be98fb1efafd9f2cfc1,

title = "Exploiting p-Fold Symmetries for Faster Polynomial Equation Solving",

abstract = "Numerous geometric problems in computer vision in- volve the solution of systems of polynomial equations. This is true for problems with minimal information, but also for finding stationary points for overdetermined problems. The state-of-the-art is based on the use of numerical linear algebra on the large but sparse co- efficient matrix that represents the expanded original equation set. In this paper we present two simplifica- tions that can be used (i) if the zero vector is one of the solutions or (ii) if the equations display certain p- fold symmetries. We evaluate the simplifications on a few example problems and demonstrate that significant speed increases are possible without loosing accuracy.",

keywords = "geometry, algebra, computer vision, Polynomial equation solving",

author = "Erik Ask and Yubin Kuang and Karl {\AA}str{\"o}m",

note = "The proceedings of ICPR 2012 will in the future be available at IEEE Xplore. The page reference given above refer to the proceedings published on USB by IEEE, and distributed to the participants during the conference.; 21st International Conference on Pattern Recognition (ICPR 2012) ; Conference date: 11-11-2012 Through 15-11-2012",

year = "2012",

language = "English",

isbn = "978-4-9906441-1-6",

pages = "3232--3235",

booktitle = "21st International Conference on Pattern Recognition (ICPR 2012), Proceedings of",

publisher = "IEEE - Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

}

Exploiting p-Fold Symmetries for Faster Polynomial Equation Solving. / Ask, Erik; Kuang, Yubin; Åström, Karl.
21st International Conference on Pattern Recognition (ICPR 2012), Proceedings of. IEEE - Institute of Electrical and Electronics Engineers Inc., 2012. p. 3232-3235.

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

TY - GEN

T1 - Exploiting p-Fold Symmetries for Faster Polynomial Equation Solving

AU - Ask, Erik

AU - Kuang, Yubin

AU - Åström, Karl

N1 - The proceedings of ICPR 2012 will in the future be available at IEEE Xplore. The page reference given above refer to the proceedings published on USB by IEEE, and distributed to the participants during the conference.

PY - 2012

Y1 - 2012

N2 - Numerous geometric problems in computer vision in- volve the solution of systems of polynomial equations. This is true for problems with minimal information, but also for finding stationary points for overdetermined problems. The state-of-the-art is based on the use of numerical linear algebra on the large but sparse co- efficient matrix that represents the expanded original equation set. In this paper we present two simplifica- tions that can be used (i) if the zero vector is one of the solutions or (ii) if the equations display certain p- fold symmetries. We evaluate the simplifications on a few example problems and demonstrate that significant speed increases are possible without loosing accuracy.

AB - Numerous geometric problems in computer vision in- volve the solution of systems of polynomial equations. This is true for problems with minimal information, but also for finding stationary points for overdetermined problems. The state-of-the-art is based on the use of numerical linear algebra on the large but sparse co- efficient matrix that represents the expanded original equation set. In this paper we present two simplifica- tions that can be used (i) if the zero vector is one of the solutions or (ii) if the equations display certain p- fold symmetries. We evaluate the simplifications on a few example problems and demonstrate that significant speed increases are possible without loosing accuracy.

KW - geometry

KW - algebra

KW - computer vision

KW - Polynomial equation solving

M3 - Paper in conference proceeding

SN - 978-4-9906441-1-6

SP - 3232

EP - 3235

BT - 21st International Conference on Pattern Recognition (ICPR 2012), Proceedings of

PB - IEEE - Institute of Electrical and Electronics Engineers Inc.

T2 - 21st International Conference on Pattern Recognition (ICPR 2012)

Y2 - 11 November 2012 through 15 November 2012

ER -

Exploiting p-Fold Symmetries for Faster Polynomial Equation Solving

Abstract

Conference

Bibliographical note

Subject classification (UKÄ)

Free keywords

Fingerprint

Cite this