Computational complexity of linear algebra problems with exponential size and real entries

Abstract

Exponential-size problems have not been investigated very well in complexity theory even though they appear in several applications. For example, approximating the solution of a partial differential equation requires one to raise an exponential-size matrix to a large power. We formally define linear algebra problems when the input vectors and matrices have size that is exponential in a parameter and have real number entries. We also investigate the computational complexity of these problems. We show that computing exponential-size inner product is in $\#\mathsf{P}$ and computing exponential-size matrix powering is in $\mathsf{FPSPACE}$, and these are both optimal. Furthermore, inspired from the partial differential equation motivation, we show some matrices can be converted into polynomials, and that computing polynomial powering is in $\#\mathsf{P}$, improving the matrix powering result for these matrices. We also show that some cases of polynomial powering are in $\mathsf{FP}$ with novel methods, and computing (not exponential-size) inner product and matrix powering can be done in sublinear space.