MatrixNnzStructure.cc 11.3 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
//
// Software License for AMDiS
//
// Copyright (c) 2010 Dresden University of Technology 
// All rights reserved.
// Authors: Simon Vey, Thomas Witkowski et al.
//
// This file is part of AMDiS
//
// See also license.opensource.txt in the distribution.


Thomas Witkowski's avatar
Merge.    
Thomas Witkowski committed
13
#include <algorithm>
14
15
16
17
18
19
20
#include "Global.h"
#include "DOFMatrix.h"
#include "parallel/MatrixNnzStructure.h"
#include "parallel/ParallelDofMapping.h"

namespace AMDiS {

Thomas Witkowski's avatar
Thomas Witkowski committed
21
22
23
24
25
26
  MatrixNnzStructure::~MatrixNnzStructure()
  {
    clear();
  }


27
28
29
30
31
32
33
34
35
36
37
38
39
40
  void MatrixNnzStructure::clear()
  {
    if (dnnz) {
      delete [] dnnz;
      dnnz = NULL;
    }
    
    if (onnz) {
      delete [] onnz;
      onnz = NULL;
    }
  }


41
  void MatrixNnzStructure::create(Matrix<DOFMatrix*> &mat,
42
43
				  ParallelDofMapping &rowDofMap,
				  ParallelDofMapping &colDofMap,
Thomas Witkowski's avatar
Thomas Witkowski committed
44
				  PeriodicMap *perMap,
45
				  const ElementObjectDatabase& elObjDb,
46
47
48
49
50
51
52
53
				  bool localMatrix)
  {
    FUNCNAME("MatrixNnzStructure::create()");

    int nRankRows = rowDofMap.getRankDofs();
    int rankStartRowIndex = rowDofMap.getStartDofs();

    int nRankCols = colDofMap.getRankDofs();
Thomas Witkowski's avatar
Thomas Witkowski committed
54
    int nOverallCols = colDofMap.getOverallDofs();
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
    int rankStartColIndex = colDofMap.getStartDofs();

    create(nRankRows, (!localMatrix ? nRankRows : -1));

    using mtl::tag::row; using mtl::tag::nz; using mtl::begin; using mtl::end;
    namespace traits = mtl::traits;
    typedef DOFMatrix::base_matrix_type Matrix;
    typedef traits::range_generator<row, Matrix>::type cursor_type;
    typedef traits::range_generator<nz, cursor_type>::type icursor_type;

    typedef vector<pair<int, int> > MatrixNnzEntry;
    typedef map<int, DofContainer> RankToDofContainer;

    // Stores to each rank a list of nnz entries (i.e. pairs of row and column
    // index) that this rank will send to. These nnz entries will be assembled
    // on this rank, but because the row DOFs are not DOFs of this rank they 
    // will be send to the owner of the row DOFs.
    map<int, MatrixNnzEntry> sendMatrixEntry;

    // Maps to each DOF that must be send to another rank the rank number of the
    // receiving rank.
    map<pair<DegreeOfFreedom, int>, int> sendDofToRank;

78
    int nComponents = mat.getNumRows();
79
80
81
82
83
84

    // First, create for all ranks, to which we send data to, MatrixNnzEntry 
    // object with 0 entries.
    for (int i = 0; i < nComponents; i++) {
      const FiniteElemSpace* feSpace = NULL;
      for (int j = 0; j < nComponents; j++)
85
86
	if (mat[i][j])
	  feSpace = mat[i][j]->getRowFeSpace();
87

88
89
      TEST_EXIT_DBG(feSpace)("No FE space found!\n");

90
91
92
93
94
95
96
97
98
99
100
101
102
103
      for (DofComm::Iterator it(rowDofMap.getDofComm().getRecvDofs(), feSpace);
	   !it.end(); it.nextRank()) {
	sendMatrixEntry[it.getRank()].resize(0);
	
	for (; !it.endDofIter(); it.nextDof())
	  sendDofToRank[make_pair(it.getDofIndex(), i)] = it.getRank();
      }
    }

    // Create list of ranks from which we receive data from.
    std::set<int> recvFromRank;
    for (int i = 0; i < nComponents; i++)  {
      const FiniteElemSpace* feSpace = NULL;
      for (int j = 0; j < nComponents; j++)
104
105
	if (mat[i][j])
	  feSpace = mat[i][j]->getRowFeSpace();
106
107
108
109
110
111
112
113
114
115
116

      for (DofComm::Iterator it(rowDofMap.getDofComm().getSendDofs(), feSpace);
	   !it.end(); it.nextRank())
	recvFromRank.insert(it.getRank());
    }


    // === Traverse matrices to create nnz data. ===

    for (int rowComp = 0; rowComp < nComponents; rowComp++) {
      for (int colComp = 0; colComp < nComponents; colComp++) {
117
	DOFMatrix *dofMat = mat[rowComp][colComp];
118
119
120
121
122
123

 	if (!dofMat)
	  continue;

	const FiniteElemSpace *rowFeSpace = dofMat->getRowFeSpace();
	const FiniteElemSpace *colFeSpace = dofMat->getColFeSpace();
Thomas Witkowski's avatar
Thomas Witkowski committed
124
	
125
126
	if (rowDofMap.isDefinedFor(rowComp) == false ||
	    colDofMap.isDefinedFor(colComp) == false)
Thomas Witkowski's avatar
Thomas Witkowski committed
127
	  continue;
128
129
130
131
132
133
134
135
136
137
138
139

	// === Prepare MTL4 iterators for the current DOF matrix. ===

	Matrix baseMat = dofMat->getBaseMatrix();
	traits::col<Matrix>::type col(baseMat);
	traits::const_value<Matrix>::type value(baseMat);  
	cursor_type cursor = begin<row>(baseMat);
	cursor_type cend = end<row>(baseMat);


	// === Iterate on all DOFs of the row mapping. ===

140
	DofMap::iterator rowIt = rowDofMap[rowComp].begin();
141
	DofMap::iterator rowEndIt = rowDofMap[rowComp].end();
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
	for (; rowIt != rowEndIt; ++rowIt) {

	  // Go to the corresponding matrix row (note, both the mapping and the
	  // matrix rows are stored in increasing order).
	  while (*cursor != rowIt->first)
	    ++cursor;

	  // The corresponding global matrix row index of the current row DOF.
	  int petscRowIdx = 0;
	  if (localMatrix) {
	    petscRowIdx = rowDofMap.getLocalMatIndex(rowComp, *cursor);
	  } else {
	    if (rowDofMap.isMatIndexFromGlobal())
	      petscRowIdx = rowDofMap.getMatIndex(rowComp, rowIt->second.global);
	    else
	      petscRowIdx = rowDofMap.getMatIndex(rowComp, *cursor);
	  }

160
161
162
163
164
165

	  // Set of periodic row associations (is empty, if row DOF is not 
	  // periodic.
	  std::set<int> perRowAsc;
	  if (perMap)
	    perMap->fillAssociations(rowFeSpace, rowIt->second.global, elObjDb, perRowAsc);
Thomas Witkowski's avatar
Thomas Witkowski committed
166

167

168
	  if (localMatrix || rowDofMap[rowComp].isRankDof(*cursor)) {
169
170
171
172
173
174
175
176
177
178
179
180
	    // === The current row DOF is a rank DOF, so create the       ===
	    // === corresponding nnz values directly on rank's nnz data.  ===
	    
	    // This is the local row index of the local PETSc matrix.
	    int localPetscRowIdx = petscRowIdx;

	    if (localMatrix == false)
	      localPetscRowIdx -= rankStartRowIndex;
	    
	    TEST_EXIT_DBG(localPetscRowIdx >= 0 && localPetscRowIdx < nRankRows)
	      ("Should not happen! \n Debug info: DOF = %d   globalRowIndx = %d   petscRowIdx = %d   localPetscRowIdx = %d   rStart = %d   compontens = %d from %d   nRankRows = %d\n",
	       *cursor,
181
	       rowDofMap[rowComp][*cursor].global,
182
183
184
185
186
187
188
189
190
191
192
	       petscRowIdx, 
	       localPetscRowIdx, 
	       rankStartRowIndex,
	       rowComp,
	       nComponents, 
	       nRankRows);
	    

	    if (localMatrix) {
	      for (icursor_type icursor = begin<nz>(cursor), 
		     icend = end<nz>(cursor); icursor != icend; ++icursor)
193
		if (colDofMap[colComp].isSet(col(*icursor)))
194
195
196
197
198
199
200
		  dnnz[localPetscRowIdx]++;	      
	    } else {
	      MultiIndex colDofIndex;

	      // Traverse all non zero entries in this row.
	      for (icursor_type icursor = begin<nz>(cursor), 
		     icend = end<nz>(cursor); icursor != icend; ++icursor) {
201
		if (colDofMap[colComp].find(col(*icursor), colDofIndex) == false)
202
		  continue;
Thomas Witkowski's avatar
Blbu    
Thomas Witkowski committed
203
		
204
205
		// Set of periodic row associations (is empty, if row DOF is not 
		// periodic.
Thomas Witkowski's avatar
Blbu    
Thomas Witkowski committed
206
		std::set<int> perColAsc = perRowAsc;
207
208
		if (perMap)
		  perMap->fillAssociations(colFeSpace, colDofIndex.global, elObjDb, perColAsc);
Thomas Witkowski's avatar
Blbu    
Thomas Witkowski committed
209
		
210
		if (perColAsc.empty()) {
211
		  if (colDofMap[colComp].isRankDof(col(*icursor)))
212
213
214
215
216
217
		    dnnz[localPetscRowIdx]++;
		  else
		    onnz[localPetscRowIdx]++;
		} else {
		  vector<int> newCols;
		  perMap->mapDof(colFeSpace, colDofIndex.global, perColAsc, newCols);
Thomas Witkowski's avatar
Blbu    
Thomas Witkowski committed
218
		  
219
220
221
222
223
224
225
226
227
228
229
230
231
		  for (int aa = 0; aa < newCols.size(); aa++) {
		    int petscColIdx = colDofMap.getMatIndex(colComp, newCols[aa]);
		    
		    // The row DOF is a rank DOF, if also the column is a rank DOF, 
		    // increment the diagNnz values for this row, 
		    // otherwise the offdiagNnz value.
		    if (petscColIdx >= rankStartColIndex && 
			petscColIdx < rankStartColIndex + nRankCols)
		      dnnz[localPetscRowIdx]++;
		    else
		      onnz[localPetscRowIdx]++;
		  }
		}
Thomas Witkowski's avatar
Thomas Witkowski committed
232
	      }
Thomas Witkowski's avatar
Blbu    
Thomas Witkowski committed
233
234
235
236
237
238
239
240
	      
 	      if (!perRowAsc.empty()) {
		vector<int> newRows;
		perMap->mapDof(rowFeSpace, rowIt->second.global, perRowAsc, newRows);
		
		dnnz[localPetscRowIdx] += 
		  (newRows.size() - 1) * (onnz[localPetscRowIdx] + dnnz[localPetscRowIdx]);
 	      }
241
242
243
244
245
246
247
248
249
250
251
252
253
254
	    }
	  } else {
	    // === The current row DOF is not a rank DOF, i.e., its values   ===
	    // === are also created on this rank, but afterthere they will   ===
	    // === be send to another rank. So we need to send also the      ===
	    // === corresponding nnz structure of this row to the corres-    ===
	    // === ponding rank.                                             ===
	    
	    // Send all non zero entries to the member of the row DOF.
	    int sendToRank = sendDofToRank[make_pair(*cursor, rowComp)];
	    MultiIndex colDofIndex;

	    for (icursor_type icursor = begin<nz>(cursor), 
		   icend = end<nz>(cursor); icursor != icend; ++icursor) {
255
	      if (colDofMap[colComp].find(col(*icursor), colDofIndex) == false)
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
		continue;

	      int petscColIdx = (colDofMap.isMatIndexFromGlobal() ? 
				 colDofMap.getMatIndex(colComp, colDofIndex.global) :
				 colDofMap.getMatIndex(colComp, col(*icursor)));
	      
	      sendMatrixEntry[sendToRank].
		push_back(make_pair(petscRowIdx, petscColIdx));
	    }
	    
	  } // if (isRankDof[*cursor]) ... else ...
	} // for each row in mat[i][j]
      } 
    }


    if (localMatrix == false) {
      // === Send and recv the nnz row structure to/from other ranks. ===
274
275
     
      StdMpi<MatrixNnzEntry> stdMpi(rowDofMap.getMpiComm());
276
      stdMpi.send(sendMatrixEntry);
277

278
279
280
      for (std::set<int>::iterator it = recvFromRank.begin(); 
	   it != recvFromRank.end(); ++it)
	stdMpi.recv(*it);
281
      stdMpi.startCommunication();     
282
     
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
      // === Evaluate the nnz structure this rank got from other ranks and add ===
      // === it to the PETSc nnz data structure.                               ===
      
      for (map<int, MatrixNnzEntry>::iterator it = stdMpi.getRecvData().begin();
	   it != stdMpi.getRecvData().end(); ++it) {
	if (it->second.size() > 0) {
	  for (unsigned int i = 0; i < it->second.size(); i++) {
	    int r = it->second[i].first;
	    int c = it->second[i].second;
	    
	    int localRowIdx = r - rankStartRowIndex;
	    
	    TEST_EXIT_DBG(localRowIdx >= 0 && localRowIdx < nRankRows)
	      ("Got row index %d/%d (nRankRows = %d) from rank %d. Should not happen!\n",
	       r, localRowIdx, nRankRows, it->first);
	    
	    if (c < rankStartColIndex || c >= rankStartColIndex + nRankCols)
	      onnz[localRowIdx]++;
	    else
	      dnnz[localRowIdx]++;
	  }
	}
      }
    }

    // The above algorithm for calculating the number of nnz per row over-
    // approximates the value, i.e., the number is always equal or larger to 
    // the real number of nnz values in the global parallel matrix. For small
    // matrices, the problem may arise, that the result is larger than the
    // number of elements in a row. This is fixed in the following.

Thomas Witkowski's avatar
Thomas Witkowski committed
314
315
    for (int i = 0; i < nRankRows; i++) {
      dnnz[i] = std::min(dnnz[i], nRankCols);
Thomas Witkowski's avatar
Bugfix    
Thomas Witkowski committed
316
317
      if (onnz)
	onnz[i] = std::min(onnz[i], nOverallCols - nRankCols);
Thomas Witkowski's avatar
Thomas Witkowski committed
318
    }
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335

#if (DEBUG != 0)
    int nMax = 0; 
    int nSum = 0;
    for (int i = 0; i < nRankRows; i++) {
      nMax = std::max(nMax, dnnz[i]);
      nSum += dnnz[i];
    }

    MSG("NNZ in diag block: max = %d, avrg = %.0f\n",
	nMax, (nSum > 0 ? (static_cast<double>(nSum) / nRankRows) : 0));

    if (!localMatrix) {
      nMax = 0;
      nSum = 0;

      for (int i = 0; i < nRankRows; i++) {
Thomas Witkowski's avatar
Merge.    
Thomas Witkowski committed
336
337
	nMax = std::max(nMax, onnz[i]);
	nSum += onnz[i];
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
      }

      MSG("NNZ in offdiag block: max = %d, avrg = %.0f\n",
	  nMax, (nSum > 0 ? (static_cast<double>(nSum) / nRankRows) : 0));     
    }
#endif
  }


  void MatrixNnzStructure::create(int nRows0, int nRows1)
  {
    if (nRows0 == 0)
      return;
    
    TEST_EXIT_DBG(nRows0 > 0)("Should not happen!\n");
Thomas Witkowski's avatar
Thomas Witkowski committed
353
354

    clear();
355
356
357
358
359
360
361
362
363
364
365
366
367
    
    dnnz = new int[nRows0];
    for (int i = 0; i < nRows0; i++)
      dnnz[i] = 0;
    
    if (nRows1 > 0) {
      onnz = new int[nRows1];
      for (int i = 0; i < nRows1; i++)
	onnz[i] = 0;	
    }
  }

}