Let $M$ be a real symmetric integer valued positive definite matrix with $\det(M) \geq 1$. I would like write code to compute


$$S\_M= \sum\_{x \in \mathbb{Z}^n} e^{-x^TMx}.$$


One option is to simply iterate over the vectors $x$ starting with ones with small coefficients and stop if things seem to be converging. Apart from the obvious problem of determining when to stop, this method is tremendously slow if $M$ is even $10$ by $10$. 


It is tempting to look at the integral $\int\_{x \in \mathbb{R}^n} e^{-x^TMx}\;dx$ instead but this equals $\sqrt{\frac{\pi^n}{\det(M)}}$ which is potentially a terrible approximation (it can for example be much less than $1$ where $S\_M \geq 1$).



> 
> How can one compute a good approximation for $S\_M$? Even an algorithm
>  that runs $2^n$ time would be a huge improvement over what I have
>  currently.
> 
> 
> 



How to compute $\sum_{x \in \mathbb{Z}^n} e^{-x^TMx}$ efficiently
You are trying to compute a multi-dimensional theta function, and this question is studied in depth in [this 2003 Math. Comp. article by Deconinck, Heil, Bobenko, van Hoeij,and Schmies](http://www.ams.org/journals/mcom/2004-73-247/S0025-5718-03-01609-0/S0025-5718-03-01609-0.pdf).


