Algebraic Invariants of Tensors: Algorithms and Decompositions

Abstract

This dissertation studies algorithmic techniques and decomposition theories for the algebraic invariants of tensors.Tensors are multiway grids of numbers encoding multilinear data, with widespread use across the sciences. Algebraic invariants of tensors, such as its derivation algebra, give structural insights to the tensor. The first result is a novel algorithm for computing these algebraic invariants. For tensors satisfying a regularity condition, our algorithm computes their derivation algebra in $O(n^{4.5})$ arithmetic operations, improving on the currently known $O(n^7)$ algorithm and coming within a factor of $n^{1/2}$ of the deterministic verification cost. The second result is a decomposition theorem for tensors arising as a product of two tensors. This theorem characterizes the derivation algebra of such a tensor using the algebraic invariants of its factors.