Selective Subdivision AAA

Divide and conquer strategy for the AAA algorithm. Similar to the strategy proposed in https://doi.org/10.48550/arXiv.2405.19582 for eigenvalue problems. It divides the region of interest into smaller subregions making sure that poles that are found in the parent region are also found in the subregion. If the poles have moved significantly the region is subdivided further. This way it is ensured that (almost) all poles are found accurately.

diffaaable.selective.selective_subdivision_aaa(f, domain, N=36, max_poles=400, cutoff=None, tol_aaa=1e-09, tol_pol=1e-05, suggestions=None, on_rim=False, Dmax=30, use_adaptive=True, evolutions_adaptive=5, radius_adaptive=0.0001, z_k=None, f_k=None, divide_horizontal=True, debug_plot_domains=False)

When the number of poles that need to be located is large it can be beneficial to subdivide the search domain. This function implements a recursive subdivision of the domain, that automatically terminates once the poles are found to a satisfactory degree.

Parameters:

• f (callable) – The function that the pole search is conducted on. It should accept batches of complex numbers and return a complex number per input.

• domain (Domain) – The pole search is limited to this domain.

• N (int) – The initial number of samples. If the number of samples drops below N the algorithm will add N new samples to the domain.

• max_poles (int) – The maximum number of poles that are considered valid within one search. If this number is exceeded the domain will be subdivided.

• cutoff (float) – A cutoff to avoid numerical instability due to large samples close to poles. See also diffaaable.adaptive.adaptive_aaa.

• tol_aaa (float) – The tolerance for the AAA algorithm. See also diffaaable.core.aaa.

• tol_pol (float) – The tolerance for the pole search. This is used to determine if a pole has moved significantly since the last domain subdivision.

• suggestions (array) – A list of poles that are already known. This is used internally to recursively call selective_subdivision_aaa.

• on_rim (bool) – If True, the initial samples are taken on the rim of the domain. Selecting the samples on the domain border is closely related to similar contour integral approaches. It is however generally recomended to sample within the domain (default: False).

• Dmax (int) – The maximum number of subdivisions. If this number is exceeded the algorithm will stop and return the current poles. TODO: allow the user to specify that when reaching Dmax the algorithm should return no poles to avoid false poles.

• use_adaptive (bool) – If True, the algorithm will use the adaptive AAA algorithm within the subdomains to locate the poles more accurately. The samples collected while searching the parent domain are passed to the respective subdomains to minimize computational cost. Using the adaptive aaa is generally recommended (default: True). If False, the algorithm will use the standard AAA algorithm.

• evolutions_adaptive (int) – The number of evolutions for the adaptive AAA algorithm.

• radius_adaptive (float) – The radius for the adaptive AAA algorithm. See also diffaaable.adaptive.adaptive_aaa.

• z_k (array) – The samples that have already been collected. This is used internally to recursively call selective_subdivision_aaa. It can also be used by the user to pass samples that are already known.

• f_k (array) – The function values of the samples that have already been collected. This is used internally to recursively call selective_subdivision_aaa. It can also be used by the user to pass samples that are already known.

• divide_horizontal (bool) – If True, the next domain division will be horizontal. Used internally to alternate between horizontal and vertical divisions during recursion.

• debug_plot_domains (bool) – If True, the algorithm will plot the domains that are being searched. This is useful for debugging and understanding the algorithm.

diffaaable.selective.plot_domain(domain, size=1)

Utility: Plot the domain as a rectangle.

Parameters:

• domain (Domain) – The domain to plot.

• size (float) – The relative size to scale the linewidth of the rectangle.

diffaaable.selective.reduced_domain(domain, reduction=0.9166666666666666)

Utility: Rescale the domain. Can be used to shring or enlarge the domain.

Parameters:

• domain (Domain) – The domain to rescale.

• reduction (float) – The factor by which to rescale the domain. A value of 1 will not change the domain. A value of 0.5 will shrink the domain by half. A value of 2 will enlarge the domain by a factor of 2.

diffaaable.selective.selective_subdivision_aaa(f, domain, N=36, max_poles=400, cutoff=None, tol_aaa=1e-09, tol_pol=1e-05, suggestions=None, on_rim=False, Dmax=30, use_adaptive=True, evolutions_adaptive=5, radius_adaptive=0.0001, z_k=None, f_k=None, divide_horizontal=True, debug_plot_domains=False)

When the number of poles that need to be located is large it can be beneficial to subdivide the search domain. This function implements a recursive subdivision of the domain, that automatically terminates once the poles are found to a satisfactory degree.

Parameters:

• f (callable) – The function that the pole search is conducted on. It should accept batches of complex numbers and return a complex number per input.

• domain (Domain) – The pole search is limited to this domain.

• N (int) – The initial number of samples. If the number of samples drops below N the algorithm will add N new samples to the domain.

• max_poles (int) – The maximum number of poles that are considered valid within one search. If this number is exceeded the domain will be subdivided.

• cutoff (float) – A cutoff to avoid numerical instability due to large samples close to poles. See also diffaaable.adaptive.adaptive_aaa.

• tol_aaa (float) – The tolerance for the AAA algorithm. See also diffaaable.core.aaa.

• tol_pol (float) – The tolerance for the pole search. This is used to determine if a pole has moved significantly since the last domain subdivision.

• suggestions (array) – A list of poles that are already known. This is used internally to recursively call selective_subdivision_aaa.

• on_rim (bool) – If True, the initial samples are taken on the rim of the domain. Selecting the samples on the domain border is closely related to similar contour integral approaches. It is however generally recomended to sample within the domain (default: False).

• Dmax (int) – The maximum number of subdivisions. If this number is exceeded the algorithm will stop and return the current poles. TODO: allow the user to specify that when reaching Dmax the algorithm should return no poles to avoid false poles.

• use_adaptive (bool) – If True, the algorithm will use the adaptive AAA algorithm within the subdomains to locate the poles more accurately. The samples collected while searching the parent domain are passed to the respective subdomains to minimize computational cost. Using the adaptive aaa is generally recommended (default: True). If False, the algorithm will use the standard AAA algorithm.

• evolutions_adaptive (int) – The number of evolutions for the adaptive AAA algorithm.

• radius_adaptive (float) – The radius for the adaptive AAA algorithm. See also diffaaable.adaptive.adaptive_aaa.

• z_k (array) – The samples that have already been collected. This is used internally to recursively call selective_subdivision_aaa. It can also be used by the user to pass samples that are already known.

• f_k (array) – The function values of the samples that have already been collected. This is used internally to recursively call selective_subdivision_aaa. It can also be used by the user to pass samples that are already known.

• divide_horizontal (bool) – If True, the next domain division will be horizontal. Used internally to alternate between horizontal and vertical divisions during recursion.

• debug_plot_domains (bool) – If True, the algorithm will plot the domains that are being searched. This is useful for debugging and understanding the algorithm.

diffaaable.selective.subdomains(domain, divide_horizontal, center=None)

Utility: Subdivide the domain into two subdomains.

Parameters:

• domain (Domain) – The domain to subdivide.

• divide_horizontal (bool) – If True, the domain is divided horizontally. If False, the domain is divided vertically.

• center (complex) – The center through wich to divide the domain. If None, the center is calculated as the mean of the domain.