# Way to automatically distinguish branch of roots in parametric sweep?

**URL:** <https://discourse.julialang.org/t/way-to-automatically-distinguish-branch-of-roots-in-parametric-sweep/11732>\
**Category:** Modelling & Simulations\
**Tags:** question\
**Created:** [June 17, 2018, 8:57am UTC](https://discourse.julialang.org/t/way-to-automatically-distinguish-branch-of-roots-in-parametric-sweep/11732 "2018-06-17T08:57:25Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![djsegal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djsegal/32/13752_2.png) [@djsegal](https://discourse.julialang.org/u/djsegal)\
**Post date:** [June 17, 2018, 8:57am UTC](https://discourse.julialang.org/t/way-to-automatically-distinguish-branch-of-roots-in-parametric-sweep/11732/1 "2018-06-17T08:57:25Z")

</div>

Let’s say you have some nonlinear function that you plug into a root solver to get all the roots

// where the maximum number of real roots possible \<= `N` (i.e. `N` = 3)

Then you sweep this function over `M` other values to get an array of `M` root lists (each of size `0` to `N`).

Is there a way to automatically distinguish the families of roots (i.e. assuming there are at most N families)

* * *

Through pictures,

- can you create separate lines for the two families below
- so you don’t have a saw-tooth looking function?

 ![48%20AM](https://global.discourse-cdn.com/julialang/original/3X/a/d/add7f6a11978010b8385af4852fb0336ffbec144.png)

Thanks!

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [June 17, 2018, 9:01am UTC](https://discourse.julialang.org/t/way-to-automatically-distinguish-branch-of-roots-in-parametric-sweep/11732/2 "2018-06-17T09:01:09Z")

</div>

Is this a julia question or should it go into one of the domain categories?

---

<div class="post-metadata">

**Author:** ![djsegal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djsegal/32/13752_2.png) [@djsegal](https://discourse.julialang.org/u/djsegal)\
**Post date:** [June 17, 2018, 9:03am UTC](https://discourse.julialang.org/t/way-to-automatically-distinguish-branch-of-roots-in-parametric-sweep/11732/3 "2018-06-17T09:03:11Z")

</div>

Sorry, dropping it into `Numerics`

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [June 17, 2018, 9:21am UTC](https://discourse.julialang.org/t/way-to-automatically-distinguish-branch-of-roots-in-parametric-sweep/11732/4 "2018-06-17T09:21:36Z")

</div>

If I understand correctly, you are working on a parametric rootfinding problem.

In general, given some regularity assumptions, once you have the roots for a particular parameter you can use homotopy continuation methods to find the “same” root for other parameters. I am not aware of a Julia package, but writing one is on my summer todo list.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [June 17, 2018, 12:07pm UTC](https://discourse.julialang.org/t/way-to-automatically-distinguish-branch-of-roots-in-parametric-sweep/11732/5 "2018-06-17T12:07:57Z")

</div>

You are asking about “numerical continuation”. The standard software is Auto, which desperately needs rewriting in Julia…

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [June 17, 2018, 12:08pm UTC](https://discourse.julialang.org/t/way-to-automatically-distinguish-branch-of-roots-in-parametric-sweep/11732/6 "2018-06-17T12:08:38Z")

</div>

To clarify, the name of the software is “Auto”, principal author Eusebius Doedel.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [June 17, 2018, 12:10pm UTC](https://discourse.julialang.org/t/way-to-automatically-distinguish-branch-of-roots-in-parametric-sweep/11732/7 "2018-06-17T12:10:08Z")

</div>

Once you have one solution, change the parameter a bit and look for the solution that is close. In that way you trace that “branch” of solutions. Then use the other one and trace its branch.

---

<div class="post-metadata">

**Author:** ![djsegal](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/djsegal/32/13752_2.png) [@djsegal](https://discourse.julialang.org/u/djsegal)\
**Post date:** [June 22, 2018, 10:26pm UTC](https://discourse.julialang.org/t/way-to-automatically-distinguish-branch-of-roots-in-parametric-sweep/11732/8 "2018-06-22T22:26:59Z")

</div>

Thanks for the help! I solved my simple example with this code:

- [`get_branch_lists(cur_array, cur_x_list)`](https://github.com/djsegal/Fussy.jl/blob/15b44aeabf1968e1e29b725fd868178c26c356da/src/structs/scan.jl#L113-L169)

// where `cur_array` has dimensions: `length(x_list)` by `max_roots_count`

* * *

Before explaining it quick, here are the pretty pictures (where markers denote root id):

 ![roots](https://global.discourse-cdn.com/julialang/original/3X/a/f/af1e24d1825d64bb4b39e2de659f3ef684121da9.jpeg)

* * *

Now the quick explanation.

- we find roots using `find_zeros` in `Roots.jl` (you’d have to use my [branch](https://github.com/JuliaMath/Roots.jl/pull/108) that allows the function to go complex in some regions)
- we piece together all the points that display the max root count (obviously a big assumption!)
- we fit the curves using a quadratic polynomial // i.e. a parabola 😛
- each new point is added to the closest polynomial with some pretty loose discretion

* * *

Obviously this is too simple, but it is a step in the right direction

// with no optimization (premature or otherwise)

**edit:** one way to optimize it for sure would be tracking roots and only doing `find_zeros` on mystery areas – i.e. `[a, min_root)` and `(max_root, b]`