  We propose a new numerical algorithm for computing the tensor rank
decomposition or canonical polyadic decomposition of higher-order tensors
subject to a rank and genericity constraint. Reformulating this computational
problem as a system of polynomial equations allows us to leverage recent
numerical linear algebra tools from computational algebraic geometry. We
characterize the complexity of our algorithm in terms of an algebraic property
of this polynomial system -- the multigraded regularity. We prove effective
bounds for many tensor formats and ranks, which are of independent interest for
overconstrained polynomial system solving. Moreover, we conjecture a general
formula for the multigraded regularity, yielding a (parameterized) polynomial
time complexity for the tensor rank decomposition problem in the considered
setting. Our numerical experiments show that our algorithm can outperform
state-of-the-art numerical algorithms by an order of magnitude in terms of
accuracy, computation time, and memory consumption.
