Almost all problems in scientific and engineering computing may ultimately be reduced to a host of standard problems in linear algebra (linear systems, least squares problems, eigenvalue and singular value problems, etc) and convex optimization (linear programming, semidefinite programming, geometric programming, second-order cone programming, etc). Whether one wants to solve partial differential equations, perform statistical estimation, process signals and images, forecast weather or markets, etc, these basic tools from linear algebra and convex optimization are the workhorses that allow one to do so with the aid of computers.

It is therefore tempting to expand this basic arsenal and the first steps out of the linear and convex territories are naturally into multilinear and multiconvex ones. We will argue that a major obstacle here is that issues in Theoretical Computer Science begin to play an essential role. For example, problems often become NP hard. So a careful study from the perspective of TCS is required for navigation in this new domain, and various types of polynomial-time approximation schemes, which have been largely neglected in linear algebra and convex optimization, becomes important.