Solving nonlinear polynomial systems in the barycentric Bernstein basis
We present a method for solving arbitrary systems of N nonlinear polynomials in n variables over an n-dimensional simplicial domain based on polynomial representation in the barycentric Bernstein basis and subdivision. The roots are approximated to arbitrary precision by iteratively constructing a s...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Spring Berlin/Heidelberg
2011
|
| Online Access: | http://hdl.handle.net/1721.1/65558 |
| _version_ | 1826213913498222592 |
|---|---|
| author | Reuter, Martin Mikkelsen, Tarjei Sigurd Sherbrooke, Evan C. Maekawa, Takashi Patrikalakis, Nicholas M. |
| author2 | Massachusetts Institute of Technology. Department of Mechanical Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Mechanical Engineering Reuter, Martin Mikkelsen, Tarjei Sigurd Sherbrooke, Evan C. Maekawa, Takashi Patrikalakis, Nicholas M. |
| author_sort | Reuter, Martin |
| collection | MIT |
| description | We present a method for solving arbitrary systems of N nonlinear polynomials in n variables over an n-dimensional simplicial domain based on polynomial representation in the barycentric Bernstein basis and subdivision. The roots are approximated to arbitrary precision by iteratively constructing a series of smaller bounding simplices. We use geometric subdivision to isolate multiple roots within a simplex. An algorithm implementing this method in rounded interval arithmetic is described and analyzed. We find that when the total order of polynomials is close to the maximum order of each variable, an iteration of this solver algorithm is asymptotically more efficient than the corresponding step in a similar algorithm which relies on polynomial representation in the tensor product Bernstein basis. We also discuss various implementation issues and identify topics for further study. |
| first_indexed | 2024-09-23T15:56:50Z |
| format | Article |
| id | mit-1721.1/65558 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:56:50Z |
| publishDate | 2011 |
| publisher | Spring Berlin/Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/655582022-10-02T05:16:21Z Solving nonlinear polynomial systems in the barycentric Bernstein basis Reuter, Martin Mikkelsen, Tarjei Sigurd Sherbrooke, Evan C. Maekawa, Takashi Patrikalakis, Nicholas M. Massachusetts Institute of Technology. Department of Mechanical Engineering Reuter, Martin Reuter, Martin Mikkelsen, Tarjei Sigurd Sherbrooke, Evan C. Patrikalakis, Nicholas M. We present a method for solving arbitrary systems of N nonlinear polynomials in n variables over an n-dimensional simplicial domain based on polynomial representation in the barycentric Bernstein basis and subdivision. The roots are approximated to arbitrary precision by iteratively constructing a series of smaller bounding simplices. We use geometric subdivision to isolate multiple roots within a simplex. An algorithm implementing this method in rounded interval arithmetic is described and analyzed. We find that when the total order of polynomials is close to the maximum order of each variable, an iteration of this solver algorithm is asymptotically more efficient than the corresponding step in a similar algorithm which relies on polynomial representation in the tensor product Bernstein basis. We also discuss various implementation issues and identify topics for further study. National Science Foundation (U.S.) (grant DMI-062933) Alexander von Humboldt Foundation (fellowship) 2011-08-30T19:27:06Z 2011-08-30T19:27:06Z 2007-11 Article http://purl.org/eprint/type/JournalArticle 0178-2789 1432-2315 http://hdl.handle.net/1721.1/65558 Reuter, Martin et al. “Solving Nonlinear Polynomial Systems in the Barycentric Bernstein Basis.” The Visual Computer 24.3 (2007) : 187-200. © 2007 Springer-Verlag en_US http://dx.doi.org/10.1007/s00371-007-0184-x Visual Computer Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Spring Berlin/Heidelberg Reuter |
| spellingShingle | Reuter, Martin Mikkelsen, Tarjei Sigurd Sherbrooke, Evan C. Maekawa, Takashi Patrikalakis, Nicholas M. Solving nonlinear polynomial systems in the barycentric Bernstein basis |
| title | Solving nonlinear polynomial systems in the barycentric Bernstein basis |
| title_full | Solving nonlinear polynomial systems in the barycentric Bernstein basis |
| title_fullStr | Solving nonlinear polynomial systems in the barycentric Bernstein basis |
| title_full_unstemmed | Solving nonlinear polynomial systems in the barycentric Bernstein basis |
| title_short | Solving nonlinear polynomial systems in the barycentric Bernstein basis |
| title_sort | solving nonlinear polynomial systems in the barycentric bernstein basis |
| url | http://hdl.handle.net/1721.1/65558 |
| work_keys_str_mv | AT reutermartin solvingnonlinearpolynomialsystemsinthebarycentricbernsteinbasis AT mikkelsentarjeisigurd solvingnonlinearpolynomialsystemsinthebarycentricbernsteinbasis AT sherbrookeevanc solvingnonlinearpolynomialsystemsinthebarycentricbernsteinbasis AT maekawatakashi solvingnonlinearpolynomialsystemsinthebarycentricbernsteinbasis AT patrikalakisnicholasm solvingnonlinearpolynomialsystemsinthebarycentricbernsteinbasis |