Braad, E.P. (2005) Selecting the roots of polynomial equations using combinatorial optimization. Master's Thesis / Essay, Computing Science.
|
Text
Infor_Ma_2005_EPBraad.CV.pdf - Published Version Download (1MB) | Preview |
Abstract
Given a system of two bivariate polynomials, say f(x, y) = 0 A g(x, y) = 0, we may use a computer program to approximate the roots numerically at runtime. Conventionally, this is done by eliminating y from f(x, y) = 0, which results in a univariate polynomial h(x) = 0. Solving it for x yields the roots x1 x,,. These results are substituted back into the system by f(x,, y) = 0 and g(x1, y) =0 to obtain possible solutions for y: y. y( and y. y,. Among these roots we can select one value of ythat is matched with x to form a solution (x1, Yj) to the system, and this can be repeated for each x. However, this approach is sometimes problematic. For example, in the back substitution step the equation f(x1, y) = 0 may become (near) degenerate. Moreover, we must take adequate measures to prevent a y-root to be selected more than once. In this thesis we propose and test a different approach, which does not suffer from these problems. From the system f(x, y) = 0 A g(x, y) = 0 we generate two univariate polynomials by eliminating x and, subsequently, y from f(x, y) = 0 A g(x, y) = 0, thereby obtaining hi(x) = 0 and h2(y) = 0. Both can be solved, which generates two sequences of roots x1 and yi " y. The problem is now to select the best n root pairs (x1, y) among the n2 possibilities, such that each root x and each root Y is used exactly once. Moreover, the error in the final solution should be minimised. We solve this combinatorial problem by representing it in the form of a bipartite graph, and computing its minimum-weight matching. In the last chapter we discuss a technique for extending this approach to more than two variables, thereby making it applicable to multi-variate systems.
| Item Type: | Thesis (Master's Thesis / Essay) |
|---|---|
| Degree programme: | Computing Science |
| Thesis type: | Master's Thesis / Essay |
| Language: | English |
| Date Deposited: | 15 Feb 2018 07:30 |
| Last Modified: | 15 Feb 2018 07:30 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/8904 |
Actions (login required)
 |
View Item |