17.2 ELL_Matrix Methods

The CÆSAR Code Package uses the ELL_Matrix class to contain and manipulate algebraic matrices. The following discussion assumes that A and B are matrices of dimension M×N, a_{i, j} is an element of A, x is a vector of length N, and y is a vector of length M.

The CÆSAR Code Package contains procedures to calculate matrix norms and matrix-vector products. In parallel, these operations require global communication. Matrix-vector products (MatVecs) are defined by

$$\sum_{{j=1,N}}^{}$$ (17.9)

A matrix norm is any scalar-valued function on a matrix, denoted by the double bar notation $\left\Vert\vphantom{ A }\right.$A$\left.\vphantom{ A }\right\Vert$, that satisfies these properties:

$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert$$ $$\geq$$ 0	$$\mbox{($\left\Vert A \right\Vert = 0$ iff $A = 0$)}$$  ,
$$\left\Vert\vphantom{ A+B }\right.$$A + B$$\left.\vphantom{ A+B }\right\Vert$$ $$\leq$$ $$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert$$ + $$\left\Vert\vphantom{ B }\right.$$B$$\left.\vphantom{ B }\right\Vert$$  ,
$$\left\Vert\vphantom{ sA }\right.$$sA$$\left.\vphantom{ sA }\right\Vert$$ = $$\left\vert\vphantom{ s }\right.$$s$$\left.\vphantom{ s }\right\vert$$$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert$$  ,	$$\mbox{where $s$ is a scalar}$$  .

(17.10)

A frequently used matrix norm is the Frobenius norm:

$$\left\Vert\vphantom{ A }\right. \left.\vphantom{ A }\right\Vert _{F}^{} \sqrt{{\sum_{i=1,M} \sum_{j=1,N} \left\vert a_{i,j} \right\vert^2}}$$ (17.11)

The general class of matrix norms known as the p-norms are defined in terms of vector norms by:

$$\left\Vert\vphantom{ A }\right. \left.\vphantom{ A }\right\Vert _{p}^{} \sup_{{x \neq 0}}^{} {\frac{{\left\Vert Ax \right\Vert _p}}{{\left\Vert x \right\Vert _p}}} \max_{{x: \left\Vert x \right\Vert _p=1}}^{} \left\Vert\vphantom{ Ax }\right. \left.\vphantom{ Ax }\right\Vert _{p}^{} \ge$$ (17.12)

In particular, the 1 and $\infty$ norms are the most easily calculated:

$$\left\Vert\vphantom{ A }\right. \left.\vphantom{ A }\right\Vert _{1}^{} \max_{{1 \leq j \leq N}}^{} \sum_{{i=1,M}}^{} \left\vert\vphantom{ a_{i,j} }\right. \left.\vphantom{ a_{i,j} }\right\vert$$ = (17.13)

$$\left\Vert\vphantom{ A }\right. \left.\vphantom{ A }\right\Vert _{{\infty}}^{} \max_{{1 \leq i \leq M}}^{} \sum_{{j=1,N}}^{} \left\vert\vphantom{ a_{i,j} }\right. \left.\vphantom{ a_{i,j} }\right\vert$$ = (17.14)

In general, p-norms are difficult to calculate. The 2-norm can be shown to be:

$$\left\Vert\vphantom{ A }\right. \left.\vphantom{ A }\right\Vert _{2}^{} \sqrt{{\mbox{maximum eigenvalue of} \; \; A^H A}}$$ = (17.15)

$$\sqrt{{\mbox{maximum eigenvalue of} \; \; A^T A}} \mbox{\hspace{2em} if $A$ is real}$$ = (17.16)

where A^H is the Hermitian (or complex conjugate transpose, or adjoint) of A. Calculating the 2-norm of a matrix requires an iterative procedure, and is not currently done in CÆSAR (only Frobenius, p = 1 and p = $\infty$ norms are calculated). However, CÆSAR calculates an estimate of the 2-norm as a range (or the middle of the range) using the following relationships:

$${\frac{{1}}{{\sqrt{N}}}}$$$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{F}^{}$$	$$\leq$$	$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{2}^{}$$	$$\leq$$	$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{F}^{}$$  ,
$$\max\limits_{{i,j}}^{}$$$$\left\vert\vphantom{ a_{i,j} }\right.$$ai, j$$\left.\vphantom{ a_{i,j} }\right\vert$$	$$\leq$$	$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{2}^{}$$	$$\leq$$	$$\sqrt{{MN}}$$$$\max\limits_{{i,j}}^{}$$$$\left\vert\vphantom{ a_{i,j} }\right.$$ai, j$$\left.\vphantom{ a_{i,j} }\right\vert$$  ,
$${\frac{{1}}{{\sqrt{N}}}}$$$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{{\infty}}^{}$$	$$\leq$$	$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{2}^{}$$	$$\leq$$	$$\sqrt{{M}}$$$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{{\infty}}^{}$$  ,
$${\frac{{1}}{{\sqrt{M}}}}$$$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{1}^{}$$	$$\leq$$	$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{2}^{}$$	$$\leq$$	$$\sqrt{{N}}$$$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{1}^{}$$  ,
		$$\left\Vert\vphantom{ A }\right.$$A$$\left.\vphantom{ A }\right\Vert _{2}^{}$$	$$\leq$$	$$\sqrt{{ \left\Vert A \right\Vert _1 \left\Vert A \right\Vert _{\infty}}}$$  .

(17.17)

For a similar but more complete discussion of matrix operations see Golub & Van Loan (1989).