alimanfoo / anjl

A neighbour-joining library for Python.
https://alimanfoo.github.io/anjl
MIT License
0 stars 0 forks source link

Parallelize minimisation of Q in dynamic algorithm #55

Open alimanfoo opened 1 day ago

alimanfoo commented 1 day ago
        if Q[i] > q_xy:
            # We can skip this row. The previous row optimum join criterion is greater
            # than the current global optimum, and so there is now way that this row
            # can contain a better match. This is the core optimisation of the dynamic
            # algorithm.
            continue

        # Join criterion could be lower than the current global minimum. Fully search
        # the row.
        j, q_ij, d_ij = search_row(
            D=D, S=S, Q=Q, obsolete=obsolete, i=i, coefficient=coefficient
        )

        if q_ij < q_xy:
            # Found new global minimum.
            q_xy = q_ij

It might be possible to parallelize this, with q_xy being reduced via min().

It would then require an additional final step to locate the row with minimum value of Q, then search that row to find the column which minimises Q.

It might also mean less rows are skipped.

alimanfoo commented 1 day ago

Those final steps to argmin Q, then calculate q for all values in the row, then argmin the row, also potentially parallelized.

alimanfoo commented 5 hours ago

https://stackoverflow.com/questions/61372937/avoid-race-condition-in-numba

alimanfoo commented 3 hours ago

https://jacobfilipp.com/DrDobbs/articles/DDJ/2009/0905/0905ec01/0905ec01.html