Using bipartite and multidimensional matching to select the roots of a system of polynomial equations
| Autor: | Henk Bekker, Eelco Braad, Boris Goldengorin |
|---|---|
| Přispěvatelé: | Operations Management & Operations Research |
| Jazyk: | Dutch; Flemish |
| Rok vydání: | 2005 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science, 3483, 397-406 Scopus-Elsevier Computational Science and Its Applications – ICCSA 2005 ISBN: 9783540258636 ICCSA (4) |
| ISSN: | 0302-9743 |
| Popis: | Assume that the system of two polynomial equations f(x,y) = 0 and g(x,y) = 0 has a finite number of solutions. Then the solution consists of pairs of an x-value and an y-value. In some cases conventional methods to calculate these solutions give incorrect results and are complicated to implement due to possible degeneracies and multiple roots in intermediate results. We propose and test a two-step method to avoid these complications. First all x-roots and all y-roots are calculated independently. Taking the multiplicity of the roots into account, the number of x-roots equals the number of y-roots. In the second step the x-roots and y-roots are matched by constructing a weighted bipartite graph, where the x-roots and the y-roots are the nodes of the graph, and the errors are the weights. Of this graph the minimum weight perfect matching is computed. By using a multidimensional matching method this principle may be generalized to more than two equations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|