Numerically stable algorithm for online updating vector sum

Question

Given a vector v, I want to keep track of the sum of its elements in a variable sum_v. Each element i of the vector v is a dot product of a weight vector w_i with other vectors d_i. So, every time d_i changes, so does v. I have been updating sum_v by changing it according to the change in v_i whenever d_i changes. Unfortunately, small numerical instabilities quickly add up.

What efficient techniques can I use to prevent this?

Edit: Right now, my algorithm takes constant time to update sum_v whenever d_i changes. I'd like to stay below log(n) where n is the length of v.

Answer 1

One solution is to build a complete binary tree such that the leaves each represent an element of v_i, and the parents represent the sums of their children. Changing an element of v requires logarithmic time to filter the change to sum_v, but the result is numerically stable with respect to cancelling deltas, although not to cancelling neighbouring elements of v.

It is an interesting problem to find a way to keep it numerically stable to both problems.