Numerical Methods Combining Symmetry and Sparsity for the Calculation of Homogeneous Polynomials Defined by Tensors

The homogeneous polynomial defined by a tensor, Axm−1 for x∈Rn, has been used in many recent problems in the context of tensor analysis and optimization, including the tensor eigenvalue problem, tensor equation, tensor complementary problem, tensor eigenvalue complementary problem, tensor variational inequality problem, and least element problem of polynomial inequalities defined by a tensor, among others. However, conventional computation methods use the definition directly and neglect the structural characteristics of homogeneous polynomials involving tensors, leading to a high computational burden (especially when considering iterative algorithms or large-scale problems). This motivates the need for efficient methods to reduce the complexity of relevant algorithms. First, considering the symmetry of each monomial in the canonical basis of homogeneous polynomials, we propose a calculation method using the merge tensor of the involved tensor to replace the original tensor, thus reducing the computational cost. Second, we propose a calculation method that combines sparsity to further reduce the computational cost. Finally, a simplified algorithm that avoids duplicate calculations is proposed. Extensive numerical experiments demonstrate the effectiveness of the proposed methods, which can be embedded into algorithms for use by the tensor optimization community, improving computational efficiency in magnetic resonance imaging, n-person non-cooperative games, the calculation of molecular orbitals, and so on.