Communications on Applied Mathematics and Computation ›› 2021, Vol. 3 ›› Issue (2): 281-289.doi: 10.1007/s42967-020-00103-4

• ORIGINAL PAPER • Previous Articles     Next Articles

On the Complexity of Finding Tensor Ranks

Mohsen Aliabadi1, Shmuel Friedland2   

  1. 1 Department of Mathematics, Iowa State University, 411 Morrill Road, Ames, IA 50011-2104, USA;
    2 Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Chicago, IL 60607-7045, USA
  • Received:2020-02-17 Revised:2020-11-19 Online:2021-06-20 Published:2021-05-26
  • Contact: Shmuel Friedland, Mohsen Aliabadi E-mail:friedlan@uic.edu;aliabadi@iastate.edu

Abstract: The purpose of this note is to give a linear algebra algorithm to fnd out if a rank of a given tensor over a feld $\mathbb{F}$ is at most k over the algebraic closure of $\mathbb{F}$, where k is a given positive integer. We estimate the arithmetic complexity of our algorithm.

Key words: Gauss elimination, Homogeneous polynomial, NP-hardness, Symmetric tensor, Tensor rank

CLC Number: