Bandwidth, Profile and Frontwidth of Matrix

When we discretize the partial differential equations using the Finite Volume Method (FVM), we get sets of linear algebraic equations with large sparse coefficient matrices that are solved using iterative or direct methods. There is renumberMesh utility in OpenFOAM that is used to reduce the bandwidth of the coefficient matrices by renumbering the cell label list.

The bandwidth is not a special term in OpenFOAM but it is a general concept in the field of solving linear systems of equations. In this blog post, I will try to give a description of it and other important terms such as profile and frontwidth.

Keywords: bandwidth, profile, frontwidth, renumberMesh

Definitions of bandwidth, profile and frontwidth

The definitions of these terms are clearly described in [1]. Let \(A\) be an \(N\) by \(N\) matrix with symmetric zero-nonzero structure, i.e. , \(a_{ij} \neq 0\) if and only if \(a_{ji} \neq 0\).

The \(i\)-th bandwidth of \(A\) is:

\begin{align}
\beta_i(A) = i \; – \; {\rm min}\{ j \; | \; a_{ij} \neq 0\}. \tag{1} \label{eq:ithBandwidth}
\end{align}

The bandwidth of \(A\) is defined by

\begin{align}
\beta = \beta(A) &= {\rm max} \{ \beta_i(A) \; | \; 1 \leq i \leq N\} \\
&= {\rm max} \{ |i-j| \; | \; a_{ij} \neq 0 \}. \tag{2} \label{eq:Bandwidth}
\end{align}

The quantity \(|Env(A)|\) is called the profile or the envelope size of \(A\), and is defined by:

\begin{align}
|Env(A)| = \sum_{i=1}^{N} \beta_i(A). \tag{4} \label{eq:Profile}
\end{align}

Another quantity called frontwidth is defined by the number of rows of the envelope of \(A\) which intersect column \(i\).

\begin{align}
\omega_i(A) = \{ k \; | \; k > i \; and \; \exists l \leq i \; s.t. \; a_{kl} \neq 0 \} \tag{5} \label{eq:frontwidth}
\end{align}

To estimate factorization time, a quantity called root mean square frontwidth is introduced by [2]. This quantity is given by:

\begin{align}
f = \sqrt{\frac{1}{N} \left( \sum_{i=1}^{N} \omega_i^2 \right)}. \tag{8} \label{eq:rmsFrontwidth}
\end{align}

Output of renumberMesh utility

When the renumberMesh utility is executed, the following data is reported to the screen.

Here, the band, profile and rms frontwidth correspond to \eqref{eq:Bandwidth}, \eqref{eq:Profile} and \eqref{eq:rmsFrontwidth}, respectively. We can confirm that they all decreased after renumbering the cell label using the Cuthill-McKee (CM) algorithm. The distributions of cell labels are visually compared between before and after reordering operations in Figure 1.

celllabel
Fig. 1 (Left) Before reordering, (Right) After reordering.
Source code of renumberMesh utility

The getBand function is called from the main function. The variables band, profile and rmsFrontwidth represent \eqref{eq:Bandwidth}, \eqref{eq:Profile} and \eqref{eq:rmsFrontwidth}, respectively.

References

Structure of src Directory in OpenFOAM part1

OpenFOAM の各種ライブラリのソースコードは,src ディレクトリ に設置されています.例えば,2015年のオープン CAE シンポジウムの講習会で取り上げた境界条件のライブラリ libfiniteVolume のソースコードは,src/finiteVolume/ 以下に設置されています.第1回目の今回は,以下の4つのディレクトリを取り上げます.

fvOptions

既存のソルバーのソースコードを直接編集することなく支配方程式にソース項(ポーラスメディアの抵抗ソースや熱交換器の体積熱ソースなど)を追加するなどのカスタマイズを行うことができる fvOptions 機能のライブラリ libfvOptions のソースコードが設置されています.各ソルバーが fvOptions 機能に対応しているかどうかは,ソルバーのソースコードで確認できます.下記は,simpleFoam の例です.

fvOptions で使用可能なタイプのリストを,こちらのページにまとめています.

renumber

セル番号の付け替え(Ordering)を行うための手法(Cuthill-McKeeSloan アルゴリズムなど)のソースコードが設置されています.renumberMesh ユーティリティは,このライブラリ librenumberMethods を使用して,セル番号の付け替えにより係数行列のバンド幅を小さくすることで,連立方程式の反復解法の計算時間の短縮化を図ります.デフォルトの手法である Cuthill-McKee 以外の手法を使用するためには,設定ファイルを用意し,実行時に -dict オプションでそのパスを指定します.

  • CuthillMcKee: デフォルトの手法
  • Sloan: boost C++ ライブラリの Sloan アルゴリズムを使用
  • manual
  • random
  • spring
  • structured

最初の2つの手法は,特別なパラメータ等のコントロールなしに使用することができます.それぞれ,バンド幅を小さくするのか,profile を小さくするのか等の特徴があります.

dynamicFvMesh

OpenFOAM では,メッシュの移動変形機能を Dynamic Mesh という名前で呼んでいます.並進・回転などの剛体運動,1次元方向の伸び縮み運動など,トポロジー変化を伴わないメッシュの移動変形のライブラリのソースコードが設置されています.次のスライドで詳しく説明しています.

[slideshare id=31811977&doc=openfoamdynamicmesh20140302-140302022414-phpapp01&w=500]

topoChangerFvMesh

トポロジー変化を伴うメッシュの移動変形のライブラリのソースコードが設置されています.

上記のリンクのように,OpenFOAM のリリースノートには,新機能や機能変更に関して比較的詳しい説明が記載されています.自分が使用しているバージョンに対応する情報を収集するためにも,良くチェックするようにしたいですね.

その2に続きます.