Readers are encouraged to read Fixed points of folded polynomial systems, Parts 1 and 2 first.
Computing the roots of $V_{11}$ through $V_{15}$ using step control:
Computing roots of $V_{16}$ through $V_{25}$:
Analysis of convergent seeds for cycle-$19$:
We continue to study a particular example of a folded polynomial system $$ F^{((n))}(z,w)=\underbrace{F(F(F(\cdots F))\cdots)}_{\text{n times}} $$ with $$ \begin{equation} F(z,w)=\left\{\begin{array}{l} 1-1/4 w+z^2 \\ z \end{array} \right\} \end{equation} $$ or equivalently the roots of $V_n(z,w)=F^{((n))}-\{z,w\}$. In Part 2, a method using Newton Iteration and line search was presented to compute the roots of $V_{10}$ using as seeds, roots of $V_9$. Using this method, all cycle-$10$ roots were found in about 4 seconds, a substantial improvement from $6.5$ hours using $\texttt{NSolve}$ discussed in Part 1. In this section, we apply the $\texttt{FindRoot}$ method of Part 2 towards computing the roots of $V_{11}$ through $V_{15}$. Table 1 lists the line-search parameters $\texttt{MaxRelativeStepSize}$ and $\texttt{MaxIteration}$ used to compute all roots for each function. The execution time includes the time to iterate $V_n$ roots using $V_{n-1}$ seeds, deleting duplicates, sorting, folding, and computing the cycle report. Note in particular, through experiment, the relative Step Size was reduced from $1/2$ used to compute the cycle-$10$ roots to $1/5$ and then to $1/10$ for the higher-folded systems, and the maximum iterations was increased to $700$ to find all $32{\small,}730$ cycle-$15$ roots.
$$ \begin{array}{c} \begin{array}{|c|c|c|c|} \hline \text{n} & \text{Size} &\text{rel Step Size} & \text{max Iter } & \text{Time (min)} \\ \hline 11 & 2046 & 1/5 & 500 & 0.2\\ 12 & 4020 & 1/4 & 500 & 0.7\\ 13 & 8190 & 1/4 & 500 & 2\\ 14 & 16{\small,}254 & 1/4 & 500 & 5.8\\ 15 & 32{\small,}730 & 1/10 & 700 & 19.2\\ \hline \end{array} \\ \text{Table 1: Timing and set up to compute roots of $V_{11}$ through $V_{15}$} \\ \end{array} $$
Rather than use a single set of cycle roots as seeds, we can find more roots if we use multiple cycles. We can start by computing the roots of $V_{n}$, using the set of cycle-$k$ seeds such that $k$ does not divide $n$. This set is called $\overline{D_n}$. For example, $\overline{D_{16}}=\{3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15\}$.
$$ \begin{array}{c} \begin{array}{|c|c|c|c|c|c|c|} \hline \text{n} & \text{Roots found} &\text{rel Step Size} & \text{max Iter } & \text{Time (min)} & \text{seeds} \\ \hline 16 & 65{\small,}280/65{\small,}280 & 1/15 & 500 & 58 & \overline{D_{16}} \\ 17 & 131{\small,}036/131{\small,}070 & 1/20 & 500 & 202 &\overline{D_{17}} \\ \hline \end{array} \\ \text{Table 2: Timing and set up to compute roots of $V_{16}$ and $V_{17}$ with step control}\\ \end{array} $$All cycle-$16$ roots are found with step size set to $1/15$ and seeds $\overline{D_{16}}$. However, even with a smaller step size, this method fails, after $3.3$ hours, to find all $13{\small,}1070$ cycle-$17$ roots. We could decrease the step size further with a corresponding increase in timing but this approach would quickly become overly time-consuming for higher folded roots.
We can however, quickly find a subset of roots by forgoing step control. We begin by computing $V_{18}$ roots with $500$ digits of working precision using the $131{\small,}070$ roots of $V_{17}$ as seeds but this time without step control. This of course reduces the number of convergent seeds substantially but produces $26{\small,}640$ roots in about four minutes. This is followed by computing roots of $V_{19}$ through $V_{25}$ using only the previous cycle roots as seeds for each cycle. Table 3 gives the results of these computations. $$ \begin{array}{c} \begin{array}{|c|c|c|c|c|c|c|} \hline \text{n} & \text{Roots found} & \text{Time (min)} & \text{seeds} \\ \hline 18 & 26{\small,}640 & 4.2 & V_{17} \\ 19 & 27{\small,}892 & 1 & V_{18} \\ 20 & 29{\small,}600 & 1 & V_{19} \\ 21 & 30{\small,}828 & 1.1 & V_{20} \\ 22 & 32{\small,}296 & 1.2 & V_{21} \\ 23 & 33{\small,}810 & 1.3 & V_{22} \\ 24 & 35{\small,}232 & 1.4 & V_{23} \\ 25 & 36{\small,}700 & 1.5 & V_{24} \\ \hline \end{array} \\ \text{Table 3: Timing and set up to compute roots of $V_{18}$ through $V_{25}$ without step control}\\ \end{array} $$
At this point it's instructive to visually confirm a sample root is correct by generating a folded root list. For example, consider cycle-$25$ root: $$-1.590012486582681+0.071542251386732 I, -0.0896883749931917-0.9337181654879224 I.$$ Folding this root $25$ times through $F(z,w)$ produces the folded root list in Table 4 which is shown with $16$ digits for brevity. However, this is not enough accuracy to generate the results in the table. Readers interested in generating the list can use the root to $30$ digits of accuracy: $$ \begin{array}{l} -1.59001248658268112292277192374+0.07154225138673214162488329905 I, \\ -0.089688374993191654983684499613-0.933718165487922387672066718635 I \end{array} $$ Note how the first entry is equal to the last entry showing this is a cycle-$25$ fixed point of $F^{((25))}$. $$ \begin{array}{c} \begin{array}{|c|c|} \hline \text{z} & \text{w} \\ \hline -1.590012486582681+0.071542251386732 I & -0.0896883749931917-0.9337181654879224 I\\ 1.545443507503656+0.005923395325698 I & -1.590012486582681+0.071542251386732 I\\ 1.785863669918689+0.000422982850272 I& 1.545443507503656+0.005923395325698 I\\ 1.802947991745044+0.000029930579175 I& 1.785863669918689+0.000422982850272 I\\ 1.804155542561975+2.180842664*10^-6 I& 1.802947991745044+0.000029930579175 I\\ 1.804240223816078+3.86513965*10^-7 I& 1.804155542561975+2.180842664*10^-6 I\\ 1.804243899595247+8.49517420*10^-7 I& 1.804240223816078+3.86513965*10^-7 I\\ 1.804235993271922+2.968844752*10^-6 I& 1.804243899595247+8.49517420*10^-7 I\\ 1.804206544510294+0.000010500613766 I& 1.804235993271922+2.968844752*10^-6 I\\ 1.804102256825531+0.000037148340969 I& 1.804206544510294+0.000010500613766 I\\ 1.803733315575403+0.000131413658116 I& 1.804102256825531+0.000037148340969 I\\ 1.802428292240703+0.000464783301288 I& 1.803733315575403+0.000131413658116 I\\ 1.797814203752371+0.001642623729477 I& 1.802428292240703+0.000464783301288 I\\ 1.781526139940878+0.005790068719225 I& 1.797814203752371+0.001642623729477 I\\ 1.724348311458779+0.020219661618338 I& 1.781526139940878+0.005790068719225 I\\ 1.527586729529564+0.068283961559891 I& 1.724348311458779+0.020219661618338 I\\ 0.8977714389638229+0.2035644316326093 I& 1.527586729529564+0.068283961559891 I\\ -0.6173416035891251+0.3484376750273480 I& 0.8977714389638229+0.2035644316326093 I\\ -0.9647410175974270-0.4811012540126513 I& -0.6173416035891251+0.3484376750273480 I\\ -0.1463977846803454+0.8411668079702897 I& -0.9647410175974270-0.4811012540126513 I\\ -1.444944033072257-0.126014600963813 I& -0.1463977846803454+0.8411668079702897 I\\ 1.1085830252251365+0.1538763894927137 I& -1.444944033072257-0.126014600963813 I\\ 0.5665143888420664+0.3726731569900612 I &1.1085830252251365+0.1538763894927137 I\\ -1.0950924854821229+0.3837803141669576 I& 0.5665143888420664+0.3726731569900612 I\\ -0.0896883749931917-0.9337181654879224 I& -1.0950924854821229+0.3837803141669576 I\\ -1.590012486582681+0.071542251386732 I& -0.0896883749931917-0.9337181654879224 I\\ \hline \end{array}\\ \text{Table 4: Folded root list for cycle-$25$ root}\\ \end{array} $$
In the above analysis we used $26{\small,}640$ seeds of cycle-$18$ to compute $27{\small,}892$ roots of cycle-$19$ by Newton iteration without step control. Of those seeds, only $3159$ converged to a root (only by folding these roots did we obtain the final $27{\small,}892$ count of cycle-$19$ roots). In Figure 1 of Part 2, we showed how the $z$ root plots of $V_{5}$ through $V_{10}$ increasingly populated a constrained region in the $z$-plane. This process is observed to continue through higher folded systems. Figure 1 shows a $z$-plot of the $26{\small,}640$ cycle-$18$ seeds. We wish to know which of these seeds converged and to what cycle-$19$ root.
We next tally the root seeds for each convergent root. Without step control, $1922$ seeds converged to the cycle-$1$ root $-0.55428,-0.55428$ and the remaining $1237$ seeds converged to cycle-$19$ roots in a relatively small section of the $z$-plot. In Figure 2, we superimpose the convergent seeds onto Figure 1. The blue points are the seeds converging to the cycle-$1$ root and the red points are the seeds converging to the cycle-$19$ roots.
No comments:
Post a Comment