The most straight forward api will be, using a map of votes as input

votes := make(map[string]map[string]float64)

if _, ok := votes["source"]; !ok {
  votes["source"] = make(map[string]float64)
}

votes["source"]["dest"] = 1.0

ppv := PPV{votes}

// potentially expensive
ppv.run()

thinking to use this library in different languages, the wrapper should be as thin as possible.

we skip the most naive implementation to iterate through the matrix to calculate the dot product. we use numpy instead.

The following would be the most straight forward implementation, given the matrix \(V\), we will do something like..

while True:
    a = a @ v
    result_seq = a[SOURCES:, :N_DELEGATE].sum(axis=1)
    if np.sum(np.abs(result_seq - p_result)) < EPSILON:
        break
    p_result = result_seq
    i += 1

EPSILON is a constant to define ’convergence’.

so just by having 1000 delegates can be quite slow…

We want to handle at least 10,522 voters. This will never going to converge.

One thing we observed is that when we have more policies, this converges faster…

we see that policies with only 10 is slower than having 60-110 nodes…. Even the fact that it contributes to having a large voting matrix overall.

This give a hint that the balance between the sources and policies do have an effect on the computational load.

At the end it is this matrix, and we are only interested in \(V_1\) and \(V_2\).

This helps when there are lots of policies relative to sources(delegates and intermediaries)

sm_1 = v[:SOURCES, :SOURCES]
sm_2 = v[SOURCES:, :SOURCES].T

while True:

    sma_2 = sma_1 @ sm_2 + sma_2
    sma_1 = sma_1 @ sm_1

    result_sm = sma_2[:N_DELEGATE, :].sum(axis=0)

    if np.sum(np.abs(result_sm - p_result)) < EPSILON:
        break

    p_result = result_sm

    i += 1

We see the same trend here. 60-360 is faster than 10. It’s nice to see a small speed bump though.

but the differences get negligible when the number of sources gets big….

Benchmark 1: python calculate_ppv.py 500 0 50
  Time (mean ± σ):      1.706 s ±  0.091 s    [User: 14.242 s, System: 1.692 s]

Benchmark 1: python calculate_ppv.py 500 0 50
  Time (mean ± σ):      1.891 s ±  0.089 s    [User: 15.547 s, System: 1.837 s]

This case below is the worst case to the sequential version.

# sequential
  Time (mean ± σ):     24.685 s ±  0.887 s    [User: 217.134 s, System: 16.602 s]
  Range (min … max):   23.928 s … 27.032 s    10 runs
# sub matrix
  Time (mean ± σ):     27.390 s ±  2.447 s    [User: 237.191 s, System: 16.035 s]
  Range (min … max):   22.516 s … 30.215 s    10 runs

but as soon as we have more policies, breaking this up to sub matrix has some speed increase.

# sequential
  Time (mean ± σ):     12.831 s ±  1.350 s    [User: 112.784 s, System: 9.302 s]
  Range (min … max):   12.039 s … 16.446 s    10 runs
# sub matrix
  Time (mean ± σ):     12.467 s ±  0.241 s    [User: 110.049 s, System: 9.258 s]
  Range (min … max):   12.097 s … 12.904 s    10 runs

we know that we can speed things up by multipling \(V\) together, meaning we can \(V^{t+1} = V \cdot V\). Lets do this with both the sequential pattern and sub matrix.

wow, that is a x271 speed bump for larger matrices. We can still wait for 20 seconds.