Applied Computational Fluid Dynamics Techniques - Wiley Episode 1 Part 2 ppt

10 APPLIED COMPUTATIONAL FLUID DYNAMICS TECHNIQUES

Element Pass 1: Count the number of elements connected to each point

Initialize esup2(1:npoin+1)=0

do ielem=1,nelem ! Loop over the elements

do inode=1,nnode ! Loop over nodes of the element

! Update storage counter, storing ahead

ipoi1=inpoel(inode,ielem)+1

esup2(ipoi1)=esup2(ipoi1)+1

enddo

enddo

Storage/reshuffling pass 1:

do ipoin=2,npoin+1 ! Loop over the points

! Update storage counter and store

esup2(ipoin)=esup2(ipoin)+esup2(ipoin-1)

enddo

Element pass 2: Store the elements in esup1

do ielem=1,nelem ! Loop over the elements

do inode=1,nnode ! Loop over nodes of the element

! Update storage counter, storing in esup1

ipoin=inpoel(inode,ielem)

istor=esup2(ipoin)+1

esup2(ipoin)=istor

esup1(istor)=ielem

enddo

enddo

Storage/reshuffling pass 2:

do ipoin=npoin+1,2,-1 ! Loop over points, in reverse order

esup2(ipoin)=esup2(ipoin-1)

enddo

esup2( 1) =0

2.2.2. POINTS SURROUNDING POINTS

As with the number of elements that can surround a point, the number of immediate

neighbours or points surrounding a point can vary greatly for an unstructured mesh. The

best way to store this information is in a linked list. This list will be denoted by

psup1(1:mpsup), psup2(1:npoin+1),

where, as before, psup1 stores the points, and the ordering is such that the points sur￾rounding point ipoin are stored in locations psup2(ipoin)+1 to psup2(ipoin+1).

DATA STRUCTURES AND ALGORITHMS 11

The construction of psup1, psup2 makes use of the element–surrounding-point infor￾mation stored in esup1, esup2. For each point, we can find the elements that surround

it from esup1, esup2. The points belonging to these elements are the points we are

required to store. In order to avoid the repetitive storage of the same point from neighbouring

elements, a help-array of the form lpoin(1:npoin) is introduced. As will become evident

in subsequent sections, help-arrays such as lpoin play a fundamental role in the fast

construction of derived data structures. As the points are being stored in psup1 and psup2,

their entry is also recorded in the array lpoin. As new possible nearest-neighbour candidate

points emerge from the esup1, esup2 and inpoel lists, lpoin is consulted to see if they

have already been stored.

Algorithmically, psup1 and psup2 are constructed as follows:

Initialize: lpoin(1:npoin)=0

Initialize: psup2(1)=0

Initialize: istor =0

do ipoin=1,npoin ! Loop over the points

! Loop over the elements surrounding the point

do iesup=esup2(ipoin)+1,esup2(ipoin+1)

ielem=esup1(iesup) ! Element number

do inode=1,nnode ! Loop over nodes of the element

jpoin=inpoel(inode,ielem) ! Point number

if(jpoin.ne.ipoin. and .lpoin(jpoin).ne.ipoin) then

! Update storage counter, storing ahead, and mark lpoin

istor=istor+1

psup1(istor)=jpoin

lpoin(jpoin)=ipoin

endif

enddo

enddo

! Update storage counters

psup2(ipoin+1)=istor

enddo

Alternatives to the use of a help-array such as lpoin are an exhaustive (brute-force) search

every time a new candidate point appears, or hash tables (Knuth (1973)). It is hard to conceive

cases where an exhaustive search would pay off in comparison to the use of help-arrays,

except for meshes that have less than 100 points (and in this case, every algorithm will do).

Hash tables offer a more attractive alternative. The idea is to introduce an array of the form

lhash(1:mhash),

where mhash denotes the maximum possible number of entries or subdivisions of the data

range. The key idea is that one can use the sparsity of neighbours of a given point to reduce

the storage required from npoin locations for lpoin to mhash, which is typically a fixed,

relatively small number (e.g. mhash=1000). In the algorithm described above, the array

lhash replaces lpoin. Instead of storing or accessing lpoin(ipoin), one accesses

lhash(1+mod(ipoin,mhash)). In some instances, neighbouring points will have the

same entries in the hash table. These instances are recorded and an exhaustive comparison is

carried out in order to see if the same point has been stored more than once.