Re-paramétrisation et réduction des systèmes irréductibles
Résumé
Vous avez imprudemment assuré à votre chef que résoudre un système d’équations non linéaires de taille n (n équations et n inconnues) nécessite un temps proportionnel à n (vous n’étiez pas très assidu aux cours d’algorith-
mique et complexité). Pour ne pas être licencié demain matin, il ne vous reste plus que cette nuit pour résoudre un système de taille 1000. Le plus frustrant est que, si vous connaissiez la valeur de 5 inconnues clefs, alors le système se décomposerait en de nombreux sous systèmes plus petits, et serait facilement soluble. Vous vous demandez s’il ne serait pas possible d’utiliser cette décomposition, bien que vous ne connaissiez pas les valeurs des inconnues clefs. Cet article montre que c’est possible. Ceci est fait au plus bas niveau, celui des procédures d’algèbre linéaire, si bien que de nombreux solveurs peuvent bénéficier de cette décomposition. Par exemple, avec k << n inconnues clefs, le coût d’une itération de la méthode de Newton-Raphson chute de O(n³) à O(kn²).
You recklessly told your boss that to solve a nonlinear system of size n (n unknowns and n equations) requires a time proportional to n (you were not very attentive during algorithmic complexity lectures). So now, you have only
one night to solve a problem with size 1000 and not to be fired tomorrow morning. The most frustrating thing is that if you knew the values of five key unknowns, then the system would be reducible into small square subsystems and easily solvable. You wonder if it would not be possible to exploit this reducibility, even without knowing the values of 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 method relying on Hensel lifting) can benefit from this decomposition with minor modifications 3 : for example, with k ≪ n key unknowns, the cost of a Newton iteration becomes O(kn²) instead of O(n ).
mique et complexité). Pour ne pas être licencié demain matin, il ne vous reste plus que cette nuit pour résoudre un système de taille 1000. Le plus frustrant est que, si vous connaissiez la valeur de 5 inconnues clefs, alors le système se décomposerait en de nombreux sous systèmes plus petits, et serait facilement soluble. Vous vous demandez s’il ne serait pas possible d’utiliser cette décomposition, bien que vous ne connaissiez pas les valeurs des inconnues clefs. Cet article montre que c’est possible. Ceci est fait au plus bas niveau, celui des procédures d’algèbre linéaire, si bien que de nombreux solveurs peuvent bénéficier de cette décomposition. Par exemple, avec k << n inconnues clefs, le coût d’une itération de la méthode de Newton-Raphson chute de O(n³) à O(kn²).
You recklessly told your boss that to solve a nonlinear system of size n (n unknowns and n equations) requires a time proportional to n (you were not very attentive during algorithmic complexity lectures). So now, you have only
one night to solve a problem with size 1000 and not to be fired tomorrow morning. The most frustrating thing is that if you knew the values of five key unknowns, then the system would be reducible into small square subsystems and easily solvable. You wonder if it would not be possible to exploit this reducibility, even without knowing the values of 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 method relying on Hensel lifting) can benefit from this decomposition with minor modifications 3 : for example, with k ≪ n key unknowns, the cost of a Newton iteration becomes O(kn²) instead of O(n ).