2
$\begingroup$

The smallest $b\in\mathbb{Z}_0$ such that $M_{ij} = 0$ for $|i-j| > b$ is the bandwidth of a matrix $M$.

Is there also a standard name for the smallest $w\in\mathbb{Z}_{\geq 0}$ such that $M_{ki}\neq0$ and $M_{kj}\neq0$ implies $|i-j| < w$ for every row $k$ of the matrix $M\in\mathbb{R}^{m\times n}$, i.e., \begin{align*} \min\left\{w\in\mathbb{Z} \mid w\geq 0 \wedge \forall k\in\mathbb{N}_{m} \forall i,j\in\mathbb{N}_n : (M_{ki}\neq 0\wedge M_{kj}\neq 0)\Rightarrow |i-j|<w \right\}. \end{align*} In other words $w$ is the width of the largest row-section of a matrix starting and ending with a nonzero element.

Maybe I would say pattern width of the matrix if I had to choose a name. But I would rather use something standard.

I need this for description of an efficient least-squares-algorithm exploiting Givens rotations where the order of the equations and therefore the bandwidth is rather irrelevant but that constant $w$ mentioned above is crucial for the performance.

$\endgroup$

1 Answer 1

1
$\begingroup$

Dierckx mentions matrices with small pattern width (as defined in the question) in his book "Curve and surface fitting with splines". He says that such sparse matrices have band structure and denotes the pattern width as bandwidth even if this contradicts the common understanding of the notion bandwidth.

Definition 4.1 on page 55 of his book:

Let $l_i$ and $u_i$ denote the column numbers of the first and last non-zero element in row $i$ of a given $p\times q$ matrix $A$ $(p\geq q)$; then the bandwidth BAND of this matrix is defined as $\max\left(u_i-l_i+1\mid 1\leq i\leq p\right)$.

Notes:

  1. That definition fails for a matrix having rows with no non-zero elements. In his special application of spline-approximation he does not get such rows.
  2. This answer is not very satisfactory since the naming conflicts commonly accepted standards. Such conflicts may lead to misunderstandings. So, if you find a good alternative name in some publication please let me know. (After checking) I would be very happy to accept your answer!
$\endgroup$

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.