# How to avoid numerical overflow while computing a sum of products?

Suppose we have $N$ vectors $\vec{x}_1, \vec{x}_2,\dots,\vec{x}_N$. $\vec{x}_i$ is a $M$-dimensional vector: $\vec{x}_i = \left[ x_{i1}\;\; x_{i2}\;\; \dots \;\;x_{iM}\right]^T$ with all $x_{ij}>0$. We want to compute the following:

$$v_i = \frac{1}{S} \prod_{j=1}^M x_{ij}\;\;\;\;\mathrm{where}\;\;\;\;S=\sum_{i=1}^N \prod_{j=1}^M x_{ij}.$$

The problem is that $M$ is high and $x_{ij}$ values are large. So, we easily get an Inf for $\prod_{j=1}^M x_{ij}$ in a numerical computing environment such as MATLAB. One trick we can do to avoid this is to divide the numerator and denominator of $v_i$ by $x_{ij}$:

$$v_i =\frac{1}{\prod \frac{x_{1j}}{x_{ij}}+\dots+1+\dots\prod\frac{x_{Nj}}{x_{ij}}}.$$

This works because each $\prod \frac{x_{ij}}{x_{kj}}$ is a very small number compared to $x_{ij}$s. However, this solution takes a lot of time: To compute $v_i$ we need to do $N^2$ vector divisions.

Is there a more efficient solution/trick which will avoid numerical overflow ?

-
This is too old to migrate, but you might want to delete and repost on Computational Science – robjohn Jan 23 '13 at 0:40