Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_mesh_2d_renumber (d06cc)

## Purpose

nag_mesh_2d_renumber (d06cc) renumbers the vertices of a given mesh using a Gibbs method, in order the reduce the bandwidth of Finite Element matrices associated with that mesh.

## Syntax

[nnz, coor, edge, conn, irow, icol, ifail] = d06cc(nnzmax, coor, edge, conn, itrace, 'nv', nv, 'nelt', nelt, 'nedge', nedge)
[nnz, coor, edge, conn, irow, icol, ifail] = nag_mesh_2d_renumber(nnzmax, coor, edge, conn, itrace, 'nv', nv, 'nelt', nelt, 'nedge', nedge)

## Description

nag_mesh_2d_renumber (d06cc) uses a Gibbs method to renumber the vertices of a given mesh in order to reduce the bandwidth of the associated finite element matrix A$A$. This matrix has elements aij${a}_{ij}$ such that:
 aij ≠ 0 ⇒ i​ and ​j​ are vertices belonging to the same triangle. $aij≠0⇒i​ and ​j​ are vertices belonging to the same triangle.$
This function reduces the bandwidth m$m$, which is the smallest integer such that aij0${a}_{ij}\ne 0$ whenever |ij| > m$|i-j|>m$ (see Gibbs et al. (1976) for details about that method). nag_mesh_2d_renumber (d06cc) also returns the sparsity structure of the matrix associated with the renumbered mesh.
This function is derived from material in the MODULEF package from INRIA (Institut National de Recherche en Informatique et Automatique).

## References

Gibbs N E, Poole W G Jr and Stockmeyer P K (1976) An algorithm for reducing the bandwidth and profile of a sparse matrix SIAM J. Numer. Anal. 13 236–250

## Parameters

### Compulsory Input Parameters

1:     nnzmax – int64int32nag_int scalar
The maximum number of nonzero entries in the matrix based on the input mesh. It is the dimension of the arrays irow and icol as declared in the function from which nag_mesh_2d_renumber (d06cc) is called.
Constraint: 4 × nelt + nvnnzmaxnv2$4×{\mathbf{nelt}}+{\mathbf{nv}}\le {\mathbf{nnzmax}}\le {{\mathbf{nv}}}^{2}$.
2:     coor(2$2$,nv) – double array
coor(1,i)${\mathbf{coor}}\left(1,\mathit{i}\right)$ contains the x$x$ coordinate of the i$\mathit{i}$th input mesh vertex, for i = 1,2,,nv$\mathit{i}=1,2,\dots ,{\mathbf{nv}}$; while coor(2,i)${\mathbf{coor}}\left(2,\mathit{i}\right)$ contains the corresponding y$y$ coordinate.
3:     edge(3$3$,nedge) – int64int32nag_int array
The specification of the boundary or interface edges. edge(1,j)${\mathbf{edge}}\left(1,j\right)$ and edge(2,j)${\mathbf{edge}}\left(2,j\right)$ contain the vertex numbers of the two end points of the j$j$th boundary edge. edge(3,j)${\mathbf{edge}}\left(3,j\right)$ is a user-supplied tag for the j$j$th boundary or interface edge: edge(3,j) = 0${\mathbf{edge}}\left(3,j\right)=0$ for an interior edge and has a nonzero tag otherwise.
Constraint: 1edge(i,j)nv$1\le {\mathbf{edge}}\left(\mathit{i},\mathit{j}\right)\le {\mathbf{nv}}$ and edge(1,j)edge(2,j)${\mathbf{edge}}\left(1,\mathit{j}\right)\ne {\mathbf{edge}}\left(2,\mathit{j}\right)$, for i = 1,2$\mathit{i}=1,2$ and j = 1,2,,nedge$\mathit{j}=1,2,\dots ,{\mathbf{nedge}}$.
4:     conn(3$3$,nelt) – int64int32nag_int array
The connectivity of the mesh between triangles and vertices. For each triangle j$\mathit{j}$, conn(i,j)${\mathbf{conn}}\left(\mathit{i},\mathit{j}\right)$ gives the indices of its three vertices (in anticlockwise order), for i = 1,2,3$\mathit{i}=1,2,3$ and j = 1,2,,nelt$\mathit{j}=1,2,\dots ,{\mathbf{nelt}}$.
Constraint: 1conn(i,j)nv$1\le {\mathbf{conn}}\left(\mathit{i},\mathit{j}\right)\le {\mathbf{nv}}$ and conn(1,j)conn(2,j)${\mathbf{conn}}\left(1,\mathit{j}\right)\ne {\mathbf{conn}}\left(2,\mathit{j}\right)$ and conn(1,j)conn(3,j)${\mathbf{conn}}\left(1,\mathit{j}\right)\ne {\mathbf{conn}}\left(3,\mathit{j}\right)$ and conn(2,j)conn(3,j)${\mathbf{conn}}\left(2,\mathit{j}\right)\ne {\mathbf{conn}}\left(3,\mathit{j}\right)$, for i = 1,2,3$\mathit{i}=1,2,3$ and j = 1,2,,nelt$\mathit{j}=1,2,\dots ,{\mathbf{nelt}}$.
5:     itrace – int64int32nag_int scalar
The level of trace information required from nag_mesh_2d_renumber (d06cc).
itrace0${\mathbf{itrace}}\le 0$
No output is generated.
itrace = 1${\mathbf{itrace}}=1$
Information about the effect of the renumbering on the finite element matrix are output. This information includes the half bandwidth and the sparsity structure of this matrix before and after renumbering.
itrace > 1${\mathbf{itrace}}>1$
The output is similar to that produced when itrace = 1${\mathbf{itrace}}=1$ but the sparsities (for each row of the matrix, indices of nonzero entries) of the matrix before and after renumbering are also output.

### Optional Input Parameters

1:     nv – int64int32nag_int scalar
Default: The dimension of the array coor.
The total number of vertices in the input mesh.
Constraint: nv3${\mathbf{nv}}\ge 3$.
2:     nelt – int64int32nag_int scalar
Default: The dimension of the array conn.
The number of triangles in the input mesh.
Constraint: nelt2 × nv1${\mathbf{nelt}}\le 2×{\mathbf{nv}}-1$.
3:     nedge – int64int32nag_int scalar
Default: The dimension of the array edge.
The number of boundary edges in the input mesh.
Constraint: nedge1${\mathbf{nedge}}\ge 1$.

### Input Parameters Omitted from the MATLAB Interface

iwork liwork rwork lrwork

### Output Parameters

1:     nnz – int64int32nag_int scalar
The number of nonzero entries in the matrix based on the input mesh.
2:     coor(2$2$,nv) – double array
coor(1,i)${\mathbf{coor}}\left(1,\mathit{i}\right)$ will contain the x$x$ coordinate of the i$\mathit{i}$th renumbered mesh vertex, for i = 1,2,,nv$\mathit{i}=1,2,\dots ,{\mathbf{nv}}$; while coor(2,i)${\mathbf{coor}}\left(2,\mathit{i}\right)$ will contain the corresponding y$y$ coordinate.
3:     edge(3$3$,nedge) – int64int32nag_int array
The renumbered specification of the boundary or interface edges.
4:     conn(3$3$,nelt) – int64int32nag_int array
The renumbered connectivity of the mesh between triangles and vertices.
5:     irow(nnzmax) – int64int32nag_int array
6:     icol(nnzmax) – int64int32nag_int array
The first nnz elements contain the row and column indices of the nonzero elements supplied in the finite element matrix A$A$.
7:     ifail – int64int32nag_int scalar
${\mathrm{ifail}}={\mathbf{0}}$ unless the function detects an error (see [Error Indicators and Warnings]).

## Error Indicators and Warnings

Errors or warnings detected by the function:
ifail = 1${\mathbf{ifail}}=1$
 On entry, nv < 3${\mathbf{nv}}<3$, or nelt > 2 × nv − 1${\mathbf{nelt}}>2×{\mathbf{nv}}-1$, or nedge < 1${\mathbf{nedge}}<1$, or nnzmax < 4 × nelt + nv${\mathbf{nnzmax}}<4×{\mathbf{nelt}}+{\mathbf{nv}}$ or nnzmax > nv2${\mathbf{nnzmax}}>{{\mathbf{nv}}}^{2}$ or conn(i,j) < 1${\mathbf{conn}}\left(i,j\right)<1$ or conn(i,j) > nv${\mathbf{conn}}\left(i,j\right)>{\mathbf{nv}}$ for some i = 1,2,3$i=1,2,3$ and j = 1,2, … ,nelt$j=1,2,\dots ,{\mathbf{nelt}}$, or conn(1,j) = conn(2,j)${\mathbf{conn}}\left(1,j\right)={\mathbf{conn}}\left(2,j\right)$ or conn(1,j) = conn(3,j)${\mathbf{conn}}\left(1,j\right)={\mathbf{conn}}\left(3,j\right)$ or conn(2,j) = conn(3,j)${\mathbf{conn}}\left(2,j\right)={\mathbf{conn}}\left(3,j\right)$ for some j = 1,2, … ,nelt$j=1,2,\dots ,{\mathbf{nelt}}$, or edge(i,j) < 1${\mathbf{edge}}\left(i,j\right)<1$ or edge(i,j) > nv${\mathbf{edge}}\left(i,j\right)>{\mathbf{nv}}$ for some i = 1,2$i=1,2$ and j = 1,2, … ,nedge$j=1,2,\dots ,{\mathbf{nedge}}$, or edge(1,j) = edge(2,j)${\mathbf{edge}}\left(1,j\right)={\mathbf{edge}}\left(2,j\right)$ for some j = 1,2, … ,nedge$j=1,2,\dots ,{\mathbf{nedge}}$, or liwork < max (nnzmax,20 × nv)$\mathit{liwork}<\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{nnzmax}},20×{\mathbf{nv}}\right)$, or lrwork < nv$\mathit{lrwork}<{\mathbf{nv}}$.
ifail = 2${\mathbf{ifail}}=2$
A serious error has occurred during the computation of the compact sparsity of the finite element matrix or in an internal call to the renumbering function. Check the input mesh, especially the connectivity between triangles and vertices (the parameter conn). If the problem persists, contact NAG.

Not applicable.

None.

## Example

In this example, a geometry with two holes (two interior circles inside an exterior one) is considered. The geometry has been meshed using the simple incremental method (nag_mesh_2d_gen_inc (d06aa)) and it has 250$250$ vertices and 402$402$ triangles. The function nag_mesh_2d_gen_boundary (d06ba) is used to renumber the vertices, and one can see the benefit in terms of the sparsity of the finite element matrix based on the renumbered mesh.
function nag_mesh_2d_renumber_example

edge = zeros(3, 100, 'int64');
coor = zeros(2, 250);

% Define boundaries
ncirc     = 3; % 3 circles
nvertices = [40, 30, 30];
centres   = [0, 0; -0.5, 0; -0.5, 0.65];

% First circle is outer circle
csign = 1;
i1 = 0;
nvb = 0;
for icirc = 1:ncirc
for i = 0:nvertices(icirc)-1
i1 = i1+1;
theta = 2*pi*i/nvertices(icirc);
coor(1,i1) = radii(icirc)*cos(theta) + centres(icirc, 1);
coor(2,i1) = csign*radii(icirc)*sin(theta) +  centres(icirc, 2);
edge(1,i1) = i1;
edge(2,i1) = i1 + 1;
edge(3,i1) = 1;
end
edge(2,i1) = nvb + 1;
nvb = nvb + nvertices(icirc);
% Subsequent circles are inner circles
csign = -1;
end
nedge = nvb;

% Initialise mesh control parameters
bspace = zeros(1, 100);
bspace(1:nvb) = 0.05;
smooth = true;
itrace = int64(0);

nnzmax = int64(3000);

% Mesh geometry
[nv, nelt, coor, conn, ifail] = nag_mesh_2d_gen_inc(edge, coor, bspace, smooth, itrace);

% Compute the sparsity of the FE matrix from the input geometry
[nz, irow, icol, ifail] = nag_mesh_2d_sparsity(nv, nnzmax, conn, 'nelt', nelt);

if (ifail == 0)
fprintf('\nNumber of non-zero entries in input mesh:  %d\n', nz);

% Plot sparsity of input mesh
fig1 = figure('Number', 'off');
plot(irow(1:double(nz)), icol(1:double(nz)), '.');
title ('Input Mesh', 'FontSize', 14);
end

% Call the renumbering routine and get the new sparsity
[nz, coor, edge, conn, irow, icol, ifail] = ...
nag_mesh_2d_renumber(nnzmax, coor, edge, conn, itrace, 'nelt', nelt);

if (ifail == 0)
fprintf('Number of non-zero entries in output mesh: %d\n', nz);
% Plot smoothed mesh
fig2 = figure('Number', 'off');
plot(irow(1:double(nz)), icol(1:double(nz)), '.');
title ('Output Mesh', 'FontSize', 14);
end

Number of non-zero entries in input mesh:  1556
Number of non-zero entries in output mesh: 1556

function d06cc_example

edge = zeros(3, 100, 'int64');
coor = zeros(2, 250);

% Define boundaries
ncirc     = 3; % 3 circles
nvertices = [40, 30, 30];
centres   = [0, 0; -0.5, 0; -0.5, 0.65];

% First circle is outer circle
csign = 1;
i1 = 0;
nvb = 0;
for icirc = 1:ncirc
for i = 0:nvertices(icirc)-1
i1 = i1+1;
theta = 2*pi*i/nvertices(icirc);
coor(1,i1) = radii(icirc)*cos(theta) + centres(icirc, 1);
coor(2,i1) = csign*radii(icirc)*sin(theta) +  centres(icirc, 2);
edge(1,i1) = i1;
edge(2,i1) = i1 + 1;
edge(3,i1) = 1;
end
edge(2,i1) = nvb + 1;
nvb = nvb + nvertices(icirc);
% Subsequent circles are inner circles
csign = -1;
end
nedge = nvb;

% Initialise mesh control parameters
bspace = zeros(1, 100);
bspace(1:nvb) = 0.05;
smooth = true;
itrace = int64(0);

nnzmax = int64(3000);

% Mesh geometry
[nv, nelt, coor, conn, ifail] = d06aa(edge, coor, bspace, smooth, itrace);

% Compute the sparsity of the FE matrix from the input geometry
[nz, irow, icol, ifail] = d06cb(nv, nnzmax, conn, 'nelt', nelt);

if (ifail == 0)
fprintf('\nNumber of non-zero entries in input mesh:  %d\n', nz);

% Plot sparsity of input mesh
fig1 = figure('Number', 'off');
plot(irow(1:double(nz)), icol(1:double(nz)), '.');
title ('Input Mesh', 'FontSize', 14);
end

% Call the renumbering routine and get the new sparsity
[nz, coor, edge, conn, irow, icol, ifail] = ...
d06cc(nnzmax, coor, edge, conn, itrace, 'nelt', nelt);

if (ifail == 0)
fprintf('Number of non-zero entries in output mesh: %d\n', nz);
% Plot smoothed mesh
fig2 = figure('Number', 'off');
plot(irow(1:double(nz)), icol(1:double(nz)), '.');
title ('Output Mesh', 'FontSize', 14);
end

Number of non-zero entries in input mesh:  1556
Number of non-zero entries in output mesh: 1556