Hichem Barki, Dominique Michelucci, Lincong Fang, Sebti Foufou, CSE Department, College of Engineering, Qatar University, PO BOX 2713, Doha, Qatar, Qatar University, School of Information Technology, Zhejiang University of Finance & Economics, 310018 Hangzhou, China, Zhejiang University, Laboratoire Electronique, Informatique et Image [UMR6306] (Le2i), Université de Bourgogne (UB)-École Nationale Supérieure d'Arts et Métiers (ENSAM), Arts et Métiers Sciences et Technologies, HESAM Université (HESAM)-HESAM Université (HESAM)-Arts et Métiers Sciences et Technologies, HESAM Université (HESAM)-HESAM Université (HESAM)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Centre National de la Recherche Scientifique (CNRS), Zheijiang University, Laboratoire Electronique, Informatique et Image ( Le2i ), Université de Bourgogne ( UB ) -AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement-Centre National de la Recherche Scientifique ( CNRS ), Université de Bourgogne (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Arts et Métiers (ENSAM), and HESAM Université (HESAM)-HESAM Université (HESAM)-AgroSup Dijon - Institut National Supérieur des Sciences Agronomiques, de l'Alimentation et de l'Environnement
You recklessly told your boss that solving a non-linear system of size n ( n unknowns and n equations) requires a time proportional to n , as you were not very attentive during algorithmic complexity lectures. So now, you have only one night to solve a problem of big size (e.g., 1000 equations/unknowns), otherwise you will be fired in the next morning. The system is well-constrained and structurally irreducible: it does not contain any strictly smaller well-constrained subsystems. Its size is big, so the Newton-Raphson method is too slow and impractical. The most frustrating thing is that if you knew the values of a small number k ? n of key unknowns, then the system would be reducible to small square subsystems and easily solved. You wonder if it would be possible to exploit this reducibility, even without knowing the values of these few key unknowns. This article shows that it is indeed possible. This is done at the lowest level, at the linear algebra routines level, so that numerous solvers (Newton-Raphson, homotopy, and also p -adic methods relying on Hensel lifting) widely involved in geometric constraint solving and CAD applications can benefit from this decomposition with minor modifications. For instance, with k ? n key unknowns, the cost of a Newton iteration becomes O ( k n 2 ) instead of O ( n 3 ) . Several experiments showing a significant performance gain of our re-parameterization technique are reported in this paper to consolidate our theoretical findings and to motivate its practical usage for bigger systems. A new re-parameterization for reducing and unlocking irreducible geometric systems.No need for the values of the key unknowns and no limit on their number.Enabling the usage of decomposition methods on irreducible re-parameterized systems.Usage at the lowest linear Algebra level and significant performance improvement.Benefits for numerous solvers (Newton-Raphson, homotopy, p -adic methods, etc.)