• cyclic reduction
• structured doubling algorithm
• numerical linear algebra
• matrix equations
• Newton's method
• equazioni matriciali
• analisi numerica
• algebra lineare numerica
• rank-structured matrices
• Nonsymmetric algebraic Riccati equations
• Cauchy-like matrices

Consideriamo l'equazione matriciale
\[
XCX+B-AX-XE=0,
\]
dove $A \in
\R^{m \times m}$, $X,B \in
\R^{m\times n}$, $C \in
\R^{n \times m}$, $E \in \R^{n \times n}$, nota come \emph{equazione di
Riccati algebrica non
simmetrica}
(NARE).
In particolare, siamo interessati a studiare un caso particolare dell'equazione,
derivante da un problema fisico nell'ambito della teoria del trasporto
di neutroni, nel quale i coefficienti sono nella forma
\begin{equation}\begin{split}\label{defs}
\begin{aligned}
B&=ee^T, & C&=qq^T,\\
A&=\Delta-eq^T, & E& =D-qe^T\\
D&=\diag(d_1,\dotsc,d_n),& \Delta&=\diag(\delta_1,\dotsc,\delta_n),\\
d_i&=\frac{1}{cx_i(1-\alpha)},& \delta_i&=\frac{1}{cx_i(1+\alpha)},\\
e&=\mat{1 & 1 & \dotsb & 1}^T,& q_i&=\frac{w_i}{2x_i}.
\end{aligned}
\end{split}
\end{equation}

Nella tesi, esaminiamo diversi metodi iterativi noti in letteratura per il calcolo
della soluzione minimale non negativa $X^\ast$.
\begin{enumerate}
\item[(a)] il metodo di Newton [C.H. Guo--Laub, 2000],
\item[(b)] lo \emph{structured doubling algorithm} [X.X. Guo--Lin--Xu,
2006],
\item[(c)] la riduzione ciclica [Ramaswami, 1999],
\item[(d)] il metodo di Newton applicato all'iterazione di Lu [Lu, 2005].
\end{enumerate}
Utilizzando le propriet\`a delle matrici con struttura di rango, sviluppiamo
versioni specializzate dei quattro algoritmi citati per il problema
\eqref{defs}, che permettono di abbassarne il costo computazionale da $O(n^3)$
operazioni aritmetiche per passo del caso generale a $O(n^2)$. Mostriamo inoltre
come
sia
possibile applicare agli algoritmi sviluppati la \emph{tecnica di shift} [He--Meini--Rhee, 2001] per accelerare la convergenza nei cosiddetti
\emph{casi critici} del problema (cio\`e, nel caso \eqref{defs}, quando $c=1,
\alpha=0$). Gli esperimenti numerici condotti evidenziano l'efficacia
dell'approccio proposto.

Come risultato supplementare, riusciamo a dimostrare alcune interessanti
relazioni algebriche che legano gli algoritmi analizzati e forniscono nuovi
spunti per l'analisi della convergenza e lo sviluppo di nuovi
algoritmi. In particolare, proviamo che il metodo (d) calcola la
stessa iterazione del metodo (a) lavorando direttamente sui generatori della
struttura di rango delle matrici coinvolte, e che il metodo (b) coincide
essenzialmente con il metodo (c), a meno dell'applicazione di una
trasformazione preliminare dell'equazione.

We consider the matrix equation
\[
XCX+B-AX-XE=0,
\]
where $A \in
\R^{m \times m}$, $X,B \in
\R^{m\times n}$, $C \in
\R^{n \times m}$, $E \in \R^{n \times n}$, known as \emph{Nonsymmetric algebraic Riccati equation}
(NARE).
As a special case, we are interested in a Riccati equation appearing in a problem in neutron transport theory, whose coefficients are
\begin{equation}\begin{split}\label{defs}
\begin{aligned}
B&=ee^T, & C&=qq^T,\\
A&=\Delta-eq^T, & E& =D-qe^T\\
D&=\diag(d_1,\dotsc,d_n),& \Delta&=\diag(\delta_1,\dotsc,\delta_n),\\
d_i&=\frac{1}{cx_i(1-\alpha)},& \delta_i&=\frac{1}{cx_i(1+\alpha)},\\
e&=\mat{1 & 1 & \dotsb & 1}^T,& q_i&=\frac{w_i}{2x_i}.
\end{aligned}
\end{split}
\end{equation}

Several iterative methods for the calculation of the minimal nonnegative solution $X^\ast$ exist in literature. Among these, we will focus on:
\begin{enumerate}
\item[(a)] Newton's method [C.H. Guo--Laub, 2000],
\item[(b)] the \emph{structured doubling algorithm} [X.X. Guo--Lin--Xu,
2006],
\item[(c)] the cyclic reduction [Ramaswami, 1999],
\item[(d)] Newton's method applied to Lu's iteration [Lu, 2005].
\end{enumerate}
Using the properties of rank-structured matrices, we develop specialized versions of these four algorithms to deal with the problem \eqref{defs}. Their common computational cost is $O(n^2)$ per step, instead of $O(n^3)$ as in the general algorithms. We also show how to apply the \emph{shift technique} [He--Meini--Rhee, 2001] together with our specialized algorithms; this leads to faster convergence in the so-called \emph{critical cases} of the problem (that is, in \eqref{defs}, when $c=1$, $\alpha=0$). The numerical experiments performed confirm the effectiveness of our approach.

As a further result, we prove a couple of interesting algebraic relations between the algorithms, which lead to deeper insight on the existing algorithms and provide ideas for the development of new ones. More precisely, we prove that the method (d) calculates the same iterates as (a) but working directly on the displacement generators of the involved matrices, and that (b) is a special case of algorithm (c), applied after a preliminary transformation of the NARE.