Un tenseur symétrique est un tableau multidimensionnel dont les entrées sont invariantes sous toutes les permutations de ses indices et il est équivalent à un polynôme homogène dont le degré est égal à l’ordre du tenseur. Dans cette thèse, nous étudions la décomposition d’un tenseur symétrique d’ordre d, noté T , sur C en tant que somme de tenseurs symétriques de rang un, c’est-à-dire T peut être écrit comme la somme de r tenseurs d'ordre-d de puissances de u_i, où u_i ∈ C^n. . Afin d’obtenir des algorithmes efficaces, il est nécessaire d’ajouter certaines restrictions à ces tenseurs. Dans la plupart de nos algorithmes, nous traitons le cas où les u_i sont linéairement indépendants et une telle décomposition est essentiellement unique. Cela implique que le nombre de termes de la somme, r, soit au plus n, et si r = n, le tenseur est appelé diagonalisable. Étant donné un tenseur T, nous nous intéressons aux deux questions algorithmiques suivantes : 1) est-il diagonalisable ? et 2) s’il est diagonalisable, produire une décomposition. Nous répondons à la première question dans le cadre du modèle de calcul algébrique. Plus précisément, en ayant accès à un oracle pour une boîte noire représentant le polynôme homogène de degré d équivalent à un tenseur d’ordre d, T sur C, nous pouvons vérifier en temps polynomial (en n et d) dans le modèle de calcul de Blum-Shub-Smale si le tenseur est diagonalisable ou non. Nous étendons également cela au cas où le nombre de termes de la somme est strictement inférieur à n. Nous donnons également un algorithme numériquement stable qui résout approximativement la deuxième question. Plus formellement, étant donné un tenseur symétrique d’ordre 3, T , qui est diagonalisable, et un paramètre de précision souhaité ε, nous donnons un algorithme qui produit une décomposition qui est ε-proche (au sens de la norme l_2 ) de la décomposition réelle. Il s’exécute en temps linéaire et nécessite un nombre de bits polylogarithmique de précision lorsqu’il est exécuté sur une machine à précision finie.
Gratuit
Disciplines