1
$\begingroup$

Suppose $A\in\mathbb{R}^{n\times n}$ is a banded matrix, i.e., a matrix with all of its nonzero elements on the main diagonal, i.e., $\alpha_{i,i}\neq 0$, the first superdiagonal, i.e., $\alpha_{i,i+1}\neq 0$, through the $k$-th superdiagonal, i.e., $\alpha_{i,i+k}\neq 0$, the first subdiagonal, i.e., $\alpha_{i-1,i}\neq 0$, through the $k$-th subdiagonal, i.e., $\alpha_{i,i+k}\neq 0$. All elements not on these diagonal are $0$. For $k = 4$ and $ n = 15$ the pattern is

\begin{pmatrix} * & * & * & * & * & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ * & * & * & * & * & * & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ * & * & * & * & * & * & * & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ * & * & * & * & * & * & * & * & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ * & * & * & * & * & * & * & * & * & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & * & * & * & * & * & * & * & * & * & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & * & * & * & * & * & * & * & * & * & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & * & * & * & * & * & * & * & * & * & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & * & * & * & * & * & * & * & * & * & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & * & * & * & * & * & * & * & * & * & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & * & * & * & * & * & * & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & * & * & * & * & * & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & * & * & * & * & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & * & * & * & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & * & * & * & * & * \\ \end{pmatrix}

Does the matrix-vector product $y = Ax$ when $A$ is banded have a backward error and backward stability result similar to that derived for dense $A$? If so derive it and comment on the differences with the result above. If not prove why it cannot.

From what I read online, in general a banded matrix is not backward stable. Although when using a QR-based system such as QR-factorization are backward stable. Also, a banded matrix can be likened in complexity to a rectangular matrix whore row dimension is equal to the bandwidth of the bank matrix. Thus the work involved in performing operations such as multiplication falls significantly, often leading to huge savings in terms of calculation time and complexity.

Hence depending on the way we perform the matrix-vector product $y = Ax$, depending on the method we use may or may not have a backward error and backward stability result. Also I do not know how backward error and backward stability result was for a dense $A$ matrix.

Any information or suggestions is greatly appreciated.

$\endgroup$
1
$\begingroup$

Let $A = [a_{ij}] \in \mathbb{R}^{m \times n}$ be a banded matrix with $k_l$ subdiagonals and $k_u$ superdiagonals and let $x \in \mathbb{R}^n$. Assume that all entries of $A$ and $x$ are floating point numbers. In the absence of any overflow or underflow in the intermediate calculations, then the computed value $\hat{y}$ of $y = Ax \in \mathbb{R}^m$ satisfies \begin{equation} \hat{y} = (A + \Delta A)x, \quad |\Delta A| \leq \gamma_k |A|, \quad k = 1 + k_l + k_u \end{equation} where $\gamma_k = \frac{ku}{1 - ku}$ and $u$ denotes the unit round off error. As usual inequalities of the form \begin{equation} |B| \leq |A| \end{equation} should be understood in the sense that $|b_{ij}| \leq |a_{ij}|$ for all $i$ and $j$. In particular, it follows from \begin{equation} |\Delta A| \leq \gamma_k |A| \end{equation} that $|\Delta A|$ is a banded matrix with at most $k_l$ subdiagonals and $k_u$ superdiagonals. The proof hinges on the proof of the lemma which was under discussion yesterday, Backward Stability Lemma. Specifically, if $x, y \in \mathbb{R}^n$ are vectors, such that all components are floating point numbers, then in the absense of underflow or overflow during the intermediate calculations, then the computed value $\hat{s}$ of the inner product $s = x^Ty$ satisfies \begin{equation} \hat{s} = (x + \Delta x)^T y, \quad |\Delta x| \leq \gamma_n |x|. \end{equation} In this case, the value $\gamma_n$ is an overestimate which allows the lemma to be applied without further consideration in the context of dense matrix multiplication. In reality, the determining factor is not the length of the vector $x$, but the number of nonzero components, i.e. $p = \text{nnz}(x)$. As a result we have the tighter estimate of \begin{equation} \hat{s} = (x + \Delta x)^T y, \quad |\Delta x| \leq \gamma_p |x|. \end{equation} The improved estimate follows from the original estimate under the very reasonable assumption that the computer evaluates $0 \cdot x = 0$ and $x + 0 = x$ for all floating point numbers. In particular, for each row $r_i \in \mathbb{R}^n$ of the banded matrix $A$, we have a perturbation $\Delta r_i$ such that the computed value $\hat{y}_i$ of the inner product $y_i = r_i \cdot x$ \begin{equation} \hat{y}_i = (r_i + \Delta r_i)\cdot x, \quad |\Delta r_i| \leq \gamma_{p_i} |r_i|, \end{equation} where $p_i$ is the number of nonzeros in row $i$. As we usual have to assume that the calculation does not underflow or overflow. Now two observations must be made. Specifically, \begin{equation} p_i \leq 1 + k_l + k_u \end{equation} for all $i$ and while equality is possible and expected deep inside the matrix, it can not occur towards the top or the bottom of the matrix where there are necessarily fewer nonzero elements per row. Moreover, if the $j$ component of $r_i$ is zero, then the $j$th component of $\Delta r_i$ is also zero. In short, the sparsity patter of $\Delta r_i$ is inherited from $r_i$. The $i$th row of the matrix $\Delta A$ is simply the row vector $\Delta r_i$.

This completes the proof of the fact that matrix vector multiplication is an operation which is component wise backwards stable for a banded matrix.

The result and the proof generalizes immediately to general sparse matrices. The number $p$ controlling the size of the error remains the maximum number of nonzero entries per row.

You are also referring to the backward stability of the QR decomposition. In general, it is true that the computed factors $\hat{Q}$ and $\hat{R}$, satisfy \begin{equation} \hat{Q} \hat{R} = A + \Delta A \end{equation} where the $\Delta A$ satisfies \begin{equation} \| \Delta A \| \leq \epsilon \| A \| \end{equation} where $\epsilon$ is a small number which depends on the unit round off error, how the transformation was accomplished, the sparsity pattern of $A$, the matrix norm being used, etc., etc. The point is that it is the norm of the perturbation $\Delta A$ which can be bounded relative to the norm of the matrix $A$. We say that the QR decomposition is normwise backward stable. In general $\Delta A$ will be dense matrix, regardless of the sparsity pattern of $A$. There is an entire discipline in numerical analysis dedicated to the study of structured perturbations.

There are two books which I am happy to recommend. Specifically: "Accuracy and stability of numerical algorithms" by Nick Higham as well as "Matrix Computations" by Gene Golub and Charles van Loan.

$\endgroup$
  • $\begingroup$ Thanks your a boss, do you know if there is a pdf version of those books online? $\endgroup$ – Wolfy Feb 3 '16 at 18:09
  • $\begingroup$ MIT maintains a copy of the 3rd edition of Matrix Computation at web.mit.edu/ehliu/Public/sclark/… $\endgroup$ – Carl Christian Feb 3 '16 at 18:29
  • $\begingroup$ There are plenty of copies of the 2nd edition of Higham's book online, but I can not find a legitimate copy of the 1st edition. $\endgroup$ – Carl Christian Feb 3 '16 at 18:34
  • $\begingroup$ Ok great, thanks again for your help. $\endgroup$ – Wolfy Feb 3 '16 at 18:42
  • $\begingroup$ By the way, I could use some help with this problem I just posted. I am sure it is really easy for you could you help? $\endgroup$ – Wolfy Feb 4 '16 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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