# Optimal algorithm choice for mixed diagonal/dense problem

$$\text{Let}\\ A, B \in \mathbb{C}^{n \times n} \text{ and } \hat{\alpha}, \hat{\beta} \in \mathbb{C}^{n}, \hat{f} \in \mathbb{C}^{2n} \\ \text{Find }\\ \underline{\mathbf{x}} \in \mathbb{C}^{2n} \text{ such that}\\ \begin{bmatrix} A & -B\\ \hat{A} & \hat{B} \end{bmatrix} \cdot \underline{\mathbf{x}} = \hat{f}\\ \hat A = \text{diag}(\hat\alpha) ,\quad \hat B = \text{diag}(\hat\beta)$$ For all rows, only one of $\hat{\alpha}$ and $\hat{\beta}$ in this row can be zero.

So basically we are dealing with a block matrix, where the upper row consists of two fully populated, dense, complex square matrices and the lower row consists of two diagonal complex matrices. I need to solve this kind of equation system, where $n$ can be anywhere between $\approx3000$ and $\approx 20000$.

I have thought about using an augmented GMRES (adapted multiplication for the lower half of the block matrix), but I think I would need a solid preconditioner, because the system might be poorly conditioned.

Are there any direct algorithms that would profit from the fact that the lower half of the block matrix consists of two diagonal matrices?

• en.wikipedia.org/wiki/Schur_complement (of one of the two diagonal matrices). – Federico Poloni Jan 13 '18 at 20:37
• The diagonal matrices may also contain $0+0i$ on their diagonal or may be $0+0i$ for all entries, but at least one entry per row in the lower half of the block matrix is not $0+0i$ – java4ever Jan 14 '18 at 5:37
• If $\beta_j=0$, then $\alpha_j\neq 0$ or the matrix wouldn't be invertible; just permute column $j$ with column $n+j$ and you can reduce to the case in which $\beta$ has all nonzero entries. – Federico Poloni Jan 14 '18 at 8:49
• I think you will want to update the question to state that $\hat f \in {\mathbb C}^{2n}$ instead of ${\mathbb C}^{n}$. – Wolfgang Bangerth Jan 14 '18 at 15:34

If $\hat{\beta}_j=0$, then $\hat{\alpha}_j\neq 0$ otherwise the matrix wouldn't be invertible. So you can swap column $j$ with column $n+j$ to make sure $\hat{\beta}_j \neq 0$ (or better, as @wim suggests in the comments, $|\hat{\beta}_j| \geq |\hat{\alpha}_j|$) (and you need to swap $x_j$ and $x_{n+j}$ conformably to get an equivalent system). You can do this for all $j=1,2,\dots,n$, hence ensuring that $\hat{B}$ is nonsingular.
Then you can solve the system using the Schur complement of $\hat{B}$.
The cost of this direct algorithm is essentially that of forming the Schur complement ($O(n^2)$ flops, since two matrices are diagonal, as correctly noted by @wim) plus that of solving the linear system with it ($\frac23 n^3$ flops).
• Indeed this is a good idea. However, it is more stable to swap column $j$ with column $j+n$ if $| \hat{\beta}_j | < | \hat{\alpha}_j |$, not only if $\hat{\beta}_j=0$. In this way it is possible to form the Schur complement with the stability of partial pivoting with column permutations. Forming the Schur complement should cost only $O(n^2)$ flops because the 'hat' matrices are diagonal. – wim Jan 15 '18 at 15:12