Newer
Older
\section{Existing Pseudo-Wall Finding Method}
The SageMath Library \cite{SchmidtGithub2020} provides functions which
calculates all solutions to Problems \ref{problem:problem-statement-1}
Here is an outline of the algorithm which does this. Simplifications will be
made in the presentation to concentrate on the case we are interested in:
Problem \ref{problem:problem-statement-2}, finding all pseudo-walls when
$\beta_{-}(v)\in\QQ$ for a $v$ with positive rank.
In the next Section \ref{sect:prob2-algorithm} from the previous chapter,
a different algorithm will be presented making use of theorems from Section
with the goal of cutting down the run time.
\subsubsection{Finding possible \texorpdfstring{$r$}{r} and
\texorpdfstring{$c$}{c}}
To do this, first calculate the upper bound $r_{\mathrm{max}}$ on the ranks of tilt
semistabilisers, as given by Theorem \ref{thm:loose-bound-on-r}.
Recalling Consequence 2 of Lemma \ref{lem:pseudo_wall_numerical_tests}, we can
iterate through the possible values of $\mu(u)=\frac{c}{r}$ taking a decreasing
sequence of all fractions between $\mu(v)$ and $\beta_{-}$, whos denominators
are no large than $r_{\mathrm{max}}$ (giving a finite sequence). This can be done with
Farey sequences \cite[Chapter 6]{alma994504533502466}, for which there exist
formulae to generate.
These $\mu(u)$ values determine pairs $r,c$ up to multiples, we can then take
all multiples which satisy $0<r\leq r_{\mathrm{max}}$.
We now have a finite sequence of pairs $r,c$ for which there might be a solution
$(r,c\ell,d\ell^2)$ to our problem. In particular, any $(r,c\ell,d\ell^2)$
satisfies Consequence 2 of Lemma \ref{lem:pseudo_wall_numerical_tests}, and the
positive rank condition. What remains is to find the $d$ values which satisfy
the Bogomolov inequalities and Consequence 3 of Lemma
\ref{lem:pseudo_wall_numerical_tests}
($\chern_2^{\beta_{-}}(u)>0$).
\subsubsection{Finding \texorpdfstring{$d$}{d} for fixed \texorpdfstring{$r$}{r}
and \texorpdfstring{$c$}{c}}
$\Delta(u) \geq 0$ induces an upper bound $\frac{c^2}{2r}$ on $d$, and the
$\chern_2^{\beta_{-}}(u)>0$ condition induces a lower bound on $d$.
The values in the range can be tested individually, to check that
the rest of the conditions are satisfied.
\subsection{Limitations}
The main downside of this algorithm is that many $r$,$c$ pairs which are tested
end up not yielding any solutions for the problem.
In fact, solutions $u$ to our problem with high rank must have $\mu(u)$ close to
0 & \leq \chern_1^{\beta_{-}}(u) \leq \chern_1^{\beta_{-}}(u) \\
0 & \leq \mu(u) - \beta_{-} \leq \frac{\chern_1^{\beta_{-}}(v)}{r}
In particular, it is the $\chern_1^{\beta_{-}}(v-u) \geq 0$ condition which
fails for $r$,$c$ pairs with large $r$ and $\frac{c}{r}$ too far from $\beta_{-}$.
This condition is only checked within the internal loop.
This, along with a conservative estimate for a bound on the $r$ values (as
illustrated in Example \ref{exmpl:recurring-first}) occasionally leads to slow
computations.
Here are some benchmarks to illustrate the performance benefits of the
alternative algorithm which will later be described in Section
\ref{sect:prob2-algorithm}.
\label{table:bench-schmidt-vs-nay}
\begin{tabular}{ |r|l|l| }
\hline
Choice of $v$ on $\mathbb{P}^2$
& $(3, 2\ell, -2)$
& $(3, 2\ell, -\frac{15}{2})$ \\
\hline
\cite[\texttt{tilt.walls_left}]{SchmidtGithub2020} exec time & \sim 20s & >1hr \\
\cite{NaylorRust2023} exec time & \sim 50ms & \sim 50ms \\
\hline
\end{tabular}
\section{Computing Solutions to Problem \ref{problem:problem-statement-2}}
Alongside this thesis, there is a library \cite{NaylorRust2023}
to compute the solutions to Problem \ref{problem:problem-statement-2},
The source code is also shown in Appendix \ref{appendix:tilt-rs}, but is better
viewed digitally from source, or via the documentation \cite{naylorPseudo_tiltRust2024}
The algorithm yields solutions
$u=(r,c\ell,d\ell^2)$ to the problem as follows.
\texorpdfstring{$q=\chern^{\beta_{-}}(u)$}{q}}
Given a Chern character $v$, the domain of the problem are first verified: that
$v$ has positive rank, that it satisfies $\Delta(v) \geq 0$, and that
$\beta_{-}(v)$ is rational.
Take $\beta_{-}(v)=\frac{a_v}{n}$ in simplest terms.
Iterate over $q = \frac{b_q}{n} \in (0,\chern_1^{\beta_{-}}(v))\cap\frac{1}{n}\ZZ$.
The code used to generate the corresponding values for $b_q$ is shown in Listing
% texlab: ignore
\ref{fig:code:consideredb}.
\lstinputlisting[
float,
caption={\raggedleft\texttt{tilt_stability::left_pseudo_semistabilizers\\::considered_b_for_beta}},
label={fig:code:consideredb}
]{../tilt.rs/src/tilt_stability/considered_b_for_beta.git-untrack.rs.tex.git-untrack}
Lemma \ref{cor:rational-beta:fixed-q-semistabs-criterion} gives us any solution
$u$ has $\chern^{\beta_{-}}_1(u) = q = \frac{b_q}{n}$ for one of the values through
which we are iterating.
We can therefore reduce the problem of finding solutions to the more specialised
problem of finding the solutions $u$ with each fixed possible $q=\chern_1^\beta(u)$
The code representing this appears in Listing
% texlab: ignore
\ref{fig:code:reducingtoeachb}.
Line 16 refers to creating an objects representing the context the specialised
problem for the fixed $q$ value, with the next line `solving' the specialised
problem, which is defined next.
The code around this deals with applying this specialisation to each $q$ value
and collect up the results.
float,
caption={\raggedleft\texttt{tilt_stability::left_pseudo_semistabilizers\\::find_all}},
label={fig:code:reducingtoeachb}
]{../tilt.rs/src/tilt_stability/find_all.git-untrack.rs.tex.git-untrack}
\texorpdfstring{$r=\chern_0(u)$}{r}
for Fixed
\texorpdfstring{$q=\chern^{\beta_{-}}(u)$}{q}
Let $q=\frac{b_q}{n}$, for which we are now solving the more specialised problem of finding
solutions $u$ with $\chern_1^{\beta_{-}}(u)=q$.
Corollary \ref{cor:rational-beta:fixed-q-semistabs-criterion}
gives a lower bound for $r\coloneqq\chern_0(u)$, and
Furthermore, we can use Theorem \ref{thm:rmax_with_eps1}
to have an upper bound on $r$
If $a_v\not=0$, we can used an integer representative for its inverse modulo $n$
(as they are coprime by definition),
and use it to generate the values of $r$ within the bounds satisfying the
modular arithmetic condition.
If $a_v=0$, then we necessarily have $n=1$ in which case the modular arithmetic
condition on $n$ is vacuous, so we can just consider all $r$ within the bounds.
The code related to this process is in the \texttt{possible_r} method to the
\texttt{fixed_q_beta::ProblemData} structure which can be found in Appendix
\ref{appendix:subsubsec:fixed-q}.
Fixing $r$ and $q$ also determines $c\coloneqq\chern_1(u)$, and so we can generate
the corresponding values of $c$, as we generate the $r$ values.
It now remains to solve the problem for each of the combinations of fixed values
for $q$ and $r$ (and consequently $c$) considered.
% texlab: ignore
This is shown in Listing \ref{fig:code:reducingtoeachr}.
\lstinputlisting[
caption={\raggedleft\texttt{tilt_stability::left_pseudo_semistabilizers\\::fixed_q_beta::ProblemData::find_all}},
label={fig:code:reducingtoeachr}
]{../tilt.rs/src/tilt_stability/left_pseudo_semistabilizers/find_all.git-untrack.rs.tex.git-untrack}
\subsubsection{Iterating Over Possible
\texorpdfstring{$d=\chern_2(u)/\ell^2$}{d}
for Fixed
\texorpdfstring{$r=\chern_0(u)$}{r}
and
\texorpdfstring{$q=\chern^{\beta_{-}}(u)$}{q}
At this point we are considering a specialisation of the problem
where we are searching for solutions $u$ for fixed given values of
$q=\chern^{\beta_{-}(v)}(u)$ and
$r\coloneqq\chern_0(u)$ (and hence $c=\chern_1(u)$).
have fixed $\chern_0(u)=r$ and
Corollary \ref{cor:rational-beta:fixed-q-semistabs-criterion}
gives us that these solutions are precisely
\[
u = (r, c\ell, d\ell^2)
\qquad
\]
such that three numerical conditions are met
($\chern^{\beta_{-}}(u)>0$, $\Delta(u) \geq 0$, $\Delta(v-u) \geq 0$).
Subsection \ref{subsec:bounds-on-d}
from the previous chapter showed that these conditions are
equivalent to bounds on $d$ given by the equations
in Subsubsection \ref{subsubsect:all-bounds-on-d-prob2}
It therefore remains to just pick values
$d\in\frac{1}{\lcm(m,2n^2)}\ZZ$ within the bounds.
% texlab: ignore
Listing \ref{fig:code:solveforfixedr} is the code for solving this
specialisation of the problem, where the possible $d$ values are computed in
% texlab: ignore
Listing \ref{fig:code:possible_chern2}.
The explicit code for the bounds can be found in Appendix
\lstinputlisting[
firstnumber=37,
float,
caption={\raggedleft\texttt{tilt_stability::left_pseudo_semistabilizers\\::fixed_q_beta::fixed_r::ProblemData::find_all}},
label={fig:code:solveforfixedr}
]{../tilt.rs/src/tilt_stability/left_pseudo_semistabilizers/fixed_q_beta/find_all.git-untrack.rs.tex.git-untrack}
\lstinputlisting[
firstnumber=44,
float,
caption={\raggedleft\texttt{tilt_stability::left_pseudo_semistabilizers\\::fixed_q_beta::fixed_r::ProblemData::possible_chern2}},
label={fig:code:possible_chern2}
]{../tilt.rs/src/tilt_stability/left_pseudo_semistabilizers/fixed_q_beta/possible_chern2.git-untrack.rs.tex.git-untrack}
\subsection{Benchmarking Different Bounds}
The bounds of the ranks of solutions to Problem
\ref{problem:problem-statement-2}
given by Theorems
\ref{thm:loose-bound-on-r},
\ref{thm:rmax_with_uniform_eps},
\ref{thm:rmax_with_eps1}, have been shown in passing to be tighter than the
previous one.
However, in principle, it could be possible that this does not translate to a
decrease in computational time to find the solutions to the problem.
This could be due to a range of potential reasons:
\begin{itemize}
\item Unexpected optimisations from the compiler for a certain form of the
\item Increased complexity to computing the formulae for the tighter bounds.
\item Modern CPU architecture such as branch predictors
\cite{BranchPredictor2024} may offset the overhead of considering ranks that
turn out to be too large to have any solutions.
\end{itemize}
For relatively small Chern characters (as those appearing in examples so far),
the difference in performance between the program \cite{NaylorRust2023} when
patched with the results of the different theorems above, do not show any
significant difference in performance, with the earlier, weaker theorems occasionally
producing the results marginally faster.
Note that this program patched with Theorem \ref{thm:loose-bound-on-r} will be
using the same bound as was used in the previously existing program
\cite{SchmidtGithub2020}. However the difference of performance can be of
several orders of magnitude as illustrated in the table in Section
\ref{table:bench-schmidt-vs-nay}.
This will be attributed to the difference in programming language and algorithm,
the latter having already been discussed in that same section.
In order to see a difference between the different patches, we use the Chern
character $v=(45,54\ell,-41\frac{\ell^2}{2})$ for a smooth projective surface $X$
with a generator $\ell$ for $NS(X)$ such that $\ell^2=1$ or 2 (such as a
principally polarised surface
with $\mathrm{Pic}(\ppas) = \ZZ\ell$
or $\mathbb{P}^2$).
This example was chosen for the large rank $\chern_0(v)=45$,
but also the large Bogomolov discriminant $\Delta(v)=4761\ell^2$, which are both
indicators of the size of the bounds on the pseudo-semistabiliser ranks.
\begin{figure}
\includegraphics[width=\linewidth]{../figures/benchmark.png}
\caption{
Comparing the performance of program \cite{NaylorRust2023}
with different patches corresponding to the results of Theorems
\ref{thm:loose-bound-on-r},
\ref{thm:rmax_with_uniform_eps},
when computing solutions to Problem \ref{problem:problem-statement-2}
for $(45,54\ell,-41\frac{\ell^2}{2})$
}
\label{fig:benchmark}
\end{figure}
As shown in Figure \ref{fig:benchmark}, there can be a significant improvement
by using Theorems \ref{thm:rmax_with_uniform_eps} \ref{thm:rmax_with_eps1}
which specialise to different values of $\chern_1^{\beta_{-}(v)}(u)$
of solutions $u$ of Problem \ref{problem:problem-statement-2}.
the program to eliminate.
As for the difference between Theorems \ref{thm:rmax_with_uniform_eps}
and \ref{thm:rmax_with_eps1}, the biggest indicator is the `$n$'-value, that is,
the denominator of $\beta_{-}(v)$. For this example, it is 15.
The bound from Theorem \ref{thm:rmax_with_eps1} is roughly $1/{k_{v,q}}$ times
that of Theorem \ref{thm:rmax_with_uniform_eps}.
Note that $k_{v,q}$ iterates through all its possible values
$\{1, 2, \ldots, n\}$ cyclically.
So we could expect the average tighter bound to be approximately that of the
average looser times the mean average of $1/{k_{v,q}}$:
\begin{equation*}
\frac{1}{n} \sum_{i=1}^n \frac{1}{i}
\end{equation*}
This certainly tends to 0 for large $n$. But in the current example, with
$n=15$, this gives us approximately 0.2 for the ratio of the average tighter bound
versus the average looser.
However, the actual ratio in the benchmark shown in Figure \ref{fig:benchmark}
between the two instances of the program patched with the two corresponding
bounds is around 0.6 instead.
This is not as good as the improvement on the bound, however it is still not insignificant
for examples with larger `$n$'-value, where the execution time will
potentially be in the order of minutes, or even hours.