We make a brief note here on rules implemented in the ADP-\/\+CG solver.\hypertarget{md__readme_autotoc_md4}{}\doxysubsubsection{Target problem}\label{md__readme_autotoc_md4}
The solver targets consecutive linear systems \$A$^\wedge$kx$^\wedge$\{k, j\} = b$^\wedge$\{k, j\}, j = 1,..., r$^\wedge$k\$, where, given a sequence of LHS matrices \$A$^\wedge$k\$, we solve a set of linear systems with different RHS. \$b$^\wedge$\{k, j\}\$ using pre-\/conditioned conjugate gradient method. One feature we expect is that spectrums of \$A$^\wedge$k\$ do not change too aggressively and therefore, it is reasonable to assume that if an expensive but accurate pre-\/conditioner is computed for \$A$^\wedge$k\$, it should also be valid for several future \$A$^\wedge$\{k + 1\}, ..., A$^\wedge$\{k+\textbackslash{}tau\}\$. The above scenario is quite common for the normal equation in the interior point method \$\+ADA$^\wedge$T\$ and ADP-\/\+CG is designed for this purpose.\hypertarget{md__readme_autotoc_md5}{}\doxysubsubsection{Origin}\label{md__readme_autotoc_md5}
The ADP-\/\+CG solver is initially written to accelerate the SDP solver HDSDP \mbox{[}1\mbox{]}.\hypertarget{md__readme_autotoc_md6}{}\doxysubsubsection{Usage and documentation}\label{md__readme_autotoc_md6}
ADP-\/\+CG implements the abstract conjugate gradient method. i.\+e., no concrete of numerical linear algebra is implemented and users are expected to link their own implementations to drive the main framework to work. To allow the users to customize ADP-\/\+CG for their own purposes, ADP-\/\+CG is well-\/documented using Doxygen system. To generate the document from scratch, on can execute


\begin{DoxyCode}{0}
\DoxyCodeLine{cd ./doc}
\DoxyCodeLine{doxygen .}

\end{DoxyCode}


at the root directory and both HTML and La\+TeX documents are to be generated.\hypertarget{md__readme_autotoc_md7}{}\doxysubsubsection{A Briefing over Adaptive pre-\/conditioning}\label{md__readme_autotoc_md7}
One most critical ingredient of ADP-\/\+CG is to find {\bfseries{when to update the pre-\/conditioner}}. If the pre-\/conditioner is too outdated, it is possible that the spectrum after pre-\/conditioning gets worse. Therefore, we have to decide when to update the pre-\/conditioner.

In ADP-\/\+CG, we use a series of rules to decide whether to update the pre-\/conditioner.

First we introduce some definitions of statistics that aid our decision


\begin{DoxyEnumerate}
\item We call solution to linear systems with LHS \$A$^\wedge$k\$ a {\itshape round} indexed by \$k\$
\item A {\itshape solve} is defined by the solution of \$A$^\wedge$k x$^\wedge$\{k, j\} = b$^\wedge$\{k, j\}\$ for some \$j\$ and round \$k\$ contains \$r$^\wedge$k\$ solves

A solve is either performed by CG or direct solver
\item A {\itshape factorization} is defined by the action to factorize \$A$^\wedge$k\$ for a Cholesky pre-\/conditioner
\item The (average) solution time of a solve is defined by the (average) time spent in CG (excluding time building pre-\/conditioner)
\item The (average) factorization time is defined by the (average) time of a factorization
\item A solve is called SUCCESS if the residual norm reaches below tolerance within maximum iteration number

A solve is called MAXITER if CG exhibits convergence but residual norm fails to reach tolerance within maximum iteration number

A solve is called FAILED if CG does not exhibit convergence or there is an irreparable error (to be clarified later)
\item Given a pre-\/conditioner, its {\itshape nused} property refers to the number of rounds it has gone through without update
\item The {\itshape latesttime} property refers to the average solution time in the lastest round
\end{DoxyEnumerate}

Based on the above statistics, we now clarify the rules.


\begin{DoxyEnumerate}
\item Update of diagonal pre-\/conditioner always happens at the beginning of a round and the update of Cholesky pre-\/conditioner happens {\bfseries{either}} at the beginning a round {\bfseries{or}} within the first solve in a round
\item In the first solve of each round, if the Cholesky pre-\/conditioner is not updated at the beginning of the round, there is a chance to regret

i.\+e., if the first CG loop is not SUCCESS due to diagonal pre-\/conditioner or an outdated Cholesky pre-\/conditioner, it is allowed to perform a make-\/up Cholesky factorization step and then update the pre-\/conditioner. Note that by rule (4), the rest of the solves in this round would by done by direct solver and by rule (5), diagonal pre-\/conditioner will never be used.
\item At the beginning of each round, pre-\/conditioner is updated if one of the following criteria, checked in order, is satisfied
\begin{DoxyItemize}
\item If the system is classified as ill-\/conditioned or indefinite by some user-\/defined criterion
\item If the diagonal pre-\/conditioner is used
\item {\bfseries{If latesttime \texorpdfstring{$>$}{>} 1.\+5 average solution time + 0.\+3 average factorization time}}
\item If ADP-\/\+CG is asked to perform direct solve
\item {\bfseries{If average solution time \texorpdfstring{$>$}{>} average factorization time}}
\item If the {\itshape nused} property of the current pre-\/conditioner exceeds the user-\/defined threshold
\end{DoxyItemize}
\item If the Cholesky pre-\/conditioner is updated in round \$k\$, then all the solves in round \$k\$ after the update are solved by the direct solver
\item If CG switches to Cholesky pre-\/conditioner, it never returns to diagonal pre-\/conditioner unless requested by the user
\item The following cases result in a FAILED solve\+:
\begin{DoxyItemize}
\item If pre-\/conditioner build-\/up fails
\item If direct solve fails
\item If pre-\/conditioning step fails
\item If NAN appears in the CG solver
\end{DoxyItemize}

If FAILED occurs, the current solution is not trustworthy and the whole solution procedure stops due to irreparable error
\end{DoxyEnumerate}

Here are some extra rules tailored for the deteriorating conditioning of normal equations arising from the interior point method


\begin{DoxyEnumerate}
\item If the number of MAXITER exceeds \$\+T\$ in round \$k\$, then all the solves thereafter are solved by direct solver
\end{DoxyEnumerate}\hypertarget{md__readme_autotoc_md8}{}\doxyparagraph{Developer}\label{md__readme_autotoc_md8}
ADP-\/\+CG is written as a subroutine for HDSDP solver, which is currently maintained by Wenzhi Gao from Shanghai Universtity of Finance and Economics.

{\bfseries{References}}

\mbox{[}1\mbox{]} Gao, Wenzhi, Dongdong Ge, and Yinyu Ye. \char`\"{}\+HDSDP\+: Software for Semidefinite Programming.\char`\"{} {\itshape ar\+Xiv preprint ar\+Xiv\+:2207.\+13862} (2022). 