1
$\begingroup$

This program involves the matrix-vector computational primitive $y \leftarrow Ax$ where $x,y\in\mathbb{R}^n$ and $A\in \mathbb{R}^{n\times n}$. A is taken to be dense and banded in the two parts of the problem. Recall, there are many ways to implement the primitive. Two standard approaches are: $$\eta_i = e_i^{T}y = e_i^{T}Ax = \tilde{a}_i^{T}x, 1\leq i\leq n \ \ \text{inner product form}$$

$$y = \sum_{1}^{n}(Ae_i)(e_i^{T}x) = \sum_{1}^{n}a_i\xi_i, \ \ \text{vector triad form}$$

That task is to implement the inner product and vector triad forms for a dense A in single and double precision.

I have done this successfully but I do not understand what this question means: Are there any conditioning considerations that you must take into account when assessing the behavior of the method?

Note: Prior to this question we had to investigate the observed numerical behavior versus the stability result over a range of problem sizes. For this I perturbed the dense matrix $A$ and analyzed the change in the results on a range of problem sizes to answer this question, so I believe the question I do not understand fully is related to this.

$\endgroup$

1 Answer 1

1
$\begingroup$

There is a fundamental problem associated with computing any inner product \begin{equation} s = x^T y. \end{equation} Specifically, if the result is nearly zero, then the relative error can be arbitrarily large.

If $x, y \in \mathbb{R}^n$ are vectors of floating point numbers, then the "standard" algorithm returns $\hat{s}$ such that \begin{equation} \hat{s} = \sum_{k=1}^n x_k y_k (1 + \theta_k^{(n)}) \end{equation} where \begin{equation} |\theta_k^{(n)}| \leq \gamma_n = \frac{nu}{1 - nu}. \end{equation} This is an overestimate, but it holds without any regard for the order in which the sum is evaluated. As usual, we are assuming that the intermediate results are all within the set of floating point numbers, i.e. no underflow and no overflow. It follows that \begin{equation} |\hat{s} - s| \leq \gamma_n \sum_{k=1}^n |x_k||y_k| \end{equation} and in the event that $s \not = 0$ we have the following expression for the relative error \begin{equation} \frac{|\hat{s} - s|}{|s|} \leq \gamma_n \frac{\sum_{k=1}^n |x_k||y_k|}{\left|\sum_{k=1}^n x_k y_k\right|} \end{equation} It follows that if the inner product is nearly zero, then the relative error can be arbitrarily large. One says that the inner product is ill conditioned and defines the condition number as the ratio as of the two sums. Strictly, speaking we can only conclude that we can not be sure that the relative error is small, but in practice unless we force computers to behave, they will take any opportunity to produce garbage.

If a matrix vector product routine must deliver results where each component has a small relative error, then it is necessary to implement an inner product which is extra precise. A good reference is the following paper

http://www.oishi.info.waseda.ac.jp/~oishi/papers/OgRuOi05.pdf

$\endgroup$
1
  • $\begingroup$ In the following paper do they have anything that would for the dense matrix vector product primitive have a version that exploits higher precision accumulation? $\endgroup$
    – Wolfy
    Commented Feb 7, 2016 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .