1
$\begingroup$

$$ \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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Schur_complement (of one of the two diagonal matrices). $\endgroup$
    – Federico Poloni
    Commented Jan 13, 2018 at 20:37
  • $\begingroup$ 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$ $\endgroup$
    – java4ever
    Commented Jan 14, 2018 at 5:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – Federico Poloni
    Commented Jan 14, 2018 at 8:49
  • $\begingroup$ I think you will want to update the question to state that $\hat f \in {\mathbb C}^{2n}$ instead of ${\mathbb C}^{n}$. $\endgroup$
    – Wolfgang Bangerth
    Commented Jan 14, 2018 at 15:34

1 Answer 1

Reset to default
1
$\begingroup$

This is what I wrote in the comments, formulated as an answer.

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – wim
    Commented Jan 15, 2018 at 15:12
  • $\begingroup$ @wim Good points, I agree on both counts. $\endgroup$
    – Federico Poloni
    Commented Jan 15, 2018 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.