KratosMultiphysics
KRATOS Multiphysics (Kratos) is a framework for building parallel, multi-disciplinary simulation software, aiming at modularity, extensibility, and high performance. Kratos is written in C++, and counts with an extensive Python interface.
ilu0_preconditioner.h
Go to the documentation of this file.
1 // | / |
2 // ' / __| _` | __| _ \ __|
3 // . \ | ( | | ( |\__ `
4 // _|\_\_| \__,_|\__|\___/ ____/
5 // Multi-Physics
6 //
7 // License: BSD License
8 // Kratos default license: kratos/license.txt
9 //
10 // Main authors: Pooyan Dadvand
11 //
12 //
13 
14 
15 #if !defined(KRATOS_ILU0_PRECONDITIONER_H_INCLUDED )
16 #define KRATOS_ILU0_PRECONDITIONER_H_INCLUDED
17 
18 // System includes
19 #include <algorithm>
20 
21 // External includes
22 
23 // Project includes
24 #include "includes/define.h"
26 
27 namespace Kratos
28 {
31 
35 
39 
43 
47 
50 
52 
53 template<class TSparseSpaceType, class TDenseSpaceType>
54 class ILU0Preconditioner : public ILUPreconditioner<TSparseSpaceType, TDenseSpaceType>
55 {
56 public:
59 
62 
64 
65 
67 
69 
71 
72 
76 
79  {
80  BaseType::L = BaseType::U = NULL;
82  }
83 
84 
86 // ILU0Preconditioner(const ILU0Preconditioner& Other){}
87 
88 
91  {
92  if ( BaseType::L!=NULL) delete[] BaseType::L;
93  if (BaseType::iL!=NULL) delete[] BaseType::iL;
94  if (BaseType::jL!=NULL) delete[] BaseType::jL;
95  if ( BaseType::U!=NULL) delete[] BaseType::U;
96  if (BaseType::iU!=NULL) delete[] BaseType::iU;
97  if (BaseType::jU!=NULL) delete[] BaseType::jU;
98 
99  BaseType::L = NULL;
100  BaseType::iL = NULL;
101  BaseType::jL = NULL;
102  BaseType::U = NULL;
103  BaseType::iU = NULL;
104  BaseType::jU = NULL;
105  }
106 
107 
108 
112 
114 // ILU0Preconditioner& operator=(const ILU0Preconditioner& Other)
115 // {
116 // BaseType::operator=(Other);
117 // return *this;
118 // }
119 
120 
121 
125 
132  void Initialize(SparseMatrixType& rA, VectorType& rX, VectorType& rB) override
133  {
134  // ILU(0) preconditioner
135  // Incomplete LU factorization with same sparcity pattern as original matrix.
136  // The diagonal is included in BaseType::U. BaseType::L has non-written 1's on its diagonal.
137  // See pg 274 Iterative methods for linear systems, Yousef Saad
138  // We assume that, within a row, the entries in A are sorted by increasing j
139  const int size = TSparseSpaceType::Size(rX);
140  int i, j, indexj, oldCountL, oldCountU, newCountL, newCountU, fillL, fillU;
141  int k, indexk, indexkj, indexkjlim, jkj, indexjlim;
142  double aik;
143  bool diagFound;
144 
145  BaseType::mILUSize= size;
146  int n = size;
147  // in case a preconditioner is mistakenly initialized twice;
148  if ( BaseType::L!=NULL) delete[] BaseType::L;
149  if (BaseType::iL!=NULL) delete[] BaseType::iL;
150  if (BaseType::jL!=NULL) delete[] BaseType::jL;
151  if ( BaseType::U!=NULL) delete[] BaseType::U;
152  if (BaseType::iU!=NULL) delete[] BaseType::iU;
153  if (BaseType::jU!=NULL) delete[] BaseType::jU;
154 
155  BaseType::L = NULL;
156  BaseType::iL = NULL;
157  BaseType::jL = NULL;
158  BaseType::U = NULL;
159  BaseType::iU = NULL;
160  BaseType::jU = NULL;
161 
162 
163  // Create copy of matrix split in its BaseType::L and BaseType::U parts
164  // Traverse matrix to count elements in rows of BaseType::L, BaseType::U
165  // If there is no element in the diagonal, make room for a zero
166  BaseType::iL=new int[n+1];
167  BaseType::iU=new int[n+1];
168  for (i=0; i<n+1; i++)
169  {
170  BaseType::iL[i]=0;
171  BaseType::iU[i]=0;
172  }
173 
174  for (typename SparseMatrixType::iterator1 a_iterator = rA.begin1(); a_iterator != rA.end1(); a_iterator++)
175  {
176  i = a_iterator.index1();
177  diagFound=false;
178 #ifndef BOOST_UBLAS_NO_NESTED_CLASS_RELATION
179  for (typename SparseMatrixType::iterator2 row_iterator = a_iterator.begin() ; row_iterator != a_iterator.end() ; ++row_iterator)
180  {
181 #else
182  for ( SparseMatrixType::iterator2 row_iterator = begin(a_iterator, boost::numeric::ublas::iterator1_tag()); row_iterator != end(a_iterator, boost::numeric::ublas::iterator1_tag()); ++row_iterator )
183  {
184 #endif
185  //j= row_iterator->first; // Changed by Pooyan!!!
186  j= row_iterator.index2(); // Changed by Pooyan!!!
187  if (i<=j) BaseType::iU[i]=BaseType::iU[i]+1;
188  if (i>j) BaseType::iL[i]=BaseType::iL[i]+1;
189  if (i==j) diagFound=true;
190  }
191  if (!diagFound) BaseType::iU[i]=BaseType::iU[i]+1;
192  }
193 
194  // BaseType::iL[i] is now the number of nonzero entries in the
195  // i-th row of BaseType::L. Transform to CSR indexes
196 
197  oldCountL=0;
198  oldCountU=0;
199  for (i=0; i<n+1; i++)
200  {
201  newCountL=oldCountL+BaseType::iL[i];
202  BaseType::iL[i]=oldCountL;
203  oldCountL=newCountL;
204  newCountU=oldCountU+BaseType::iU[i];
205  BaseType::iU[i]=oldCountU;
206  oldCountU=newCountU;
207  }
208 
209  // Traverse again the matrix copying its entries
210  BaseType::L =new double[BaseType::iL[n]];
211  BaseType::jL=new int [BaseType::iL[n]];
212  BaseType::U =new double[BaseType::iU[n]];
213  BaseType::jU=new int [BaseType::iU[n]];
214  fillL=0;
215  fillU=0;
216  //for (i=0; i<n; i++) {
217  for (typename SparseMatrixType::iterator1 a_iterator = rA.begin1(); a_iterator != rA.end1(); a_iterator++)
218  {
219  i = a_iterator.index1();
220  diagFound=false;
221 #ifndef BOOST_UBLAS_NO_NESTED_CLASS_RELATION
222  for (typename SparseMatrixType::iterator2 row_iterator = a_iterator.begin() ; row_iterator != a_iterator.end() ; ++row_iterator)
223  {
224 #else
225  for ( SparseMatrixType::iterator2 row_iterator = begin(a_iterator, boost::numeric::ublas::iterator1_tag()); row_iterator != end(a_iterator, boost::numeric::ublas::iterator1_tag()); ++row_iterator )
226  {
227 #endif
228  j= row_iterator.index2(); // Changed by Pooyan!!!
229  if (i==j) diagFound=true;
230  if ( (j>i) && (!diagFound) )
231  {
232  // This row does not have a diagonal entry. Make it and put a zero.
233  BaseType::jU[fillU]=i;
234  BaseType::U[fillU]=0.00;
235  fillU++;
236  diagFound=true;
237  }
238  if (i<=j)
239  {
240  BaseType::jU[fillU]=j;
241  BaseType::U[fillU]= *row_iterator;
242  fillU++;
243  }
244  if (i>j)
245  {
246  BaseType::jL[fillL]=j;
247  BaseType::L[fillL]= *row_iterator;
248  fillL++;
249  }
250  }
251  }
252 
253 
254  // Now comes the real factorization:
255  // for i=2, ... ,n
256  // for k=1, ... ,i-1 and (i,k) in nonzero pattern
257  // a[i,k]=a[i,k]/a[k,k]
258  // for j=k+1, ... ,n and (i,j) in nonzero pattern
259  // a[i,j]=a[i,j]-a[i,k]*a[k,j]
260  // end do
261  // end do
262  // end do
263 
264 
265  for (i=1; i<n; i++)
266  {
267  for (indexk=BaseType::iL[i]; indexk<BaseType::iL[i+1]; indexk++)
268  {
269  k=BaseType::jL[indexk];
270 
272  aik=BaseType::L[indexk];
273 
274  indexkj = BaseType::iU[k ]; // traverses row k of BaseType::U
275  indexkjlim= BaseType::iU[k+1];
276  jkj = BaseType::jU[indexkj]; //Riccardo - moved within the while loop
277  while (jkj<=k) jkj=BaseType::jU[++indexkj]; // add rows only for j>k
278 //****************************************************************************************
279 //****************************************************************************************+
280 //by Riccardo ... here an array bound is broken
281 //between this line
282  indexj = indexk+1; // traverses row i of BaseType::L beyond k
283  indexjlim = BaseType::iL[i+1];
284 // j = BaseType::jL[indexj]; //Riccardo - moved within the while loop just below
285 //and this line
286 //the memory is broken in accessing to BaseType::jL[indexj]; when i=n-1
287 //when it works j is read to be 0 ... but it could be whatever value
288 //****************************************************************************************+
289 //****************************************************************************************+
290 
291  while ( (indexkj<indexkjlim) && (indexj<indexjlim) )
292  {
293  j = BaseType::jL[indexj];
294  if (j==jkj)
295  {
296  BaseType::L[indexj]= BaseType::L[indexj]-aik*BaseType::U[indexkj];
297  indexj++;
298  j=BaseType::jL[indexj];
299  indexkj++;
300  jkj=BaseType::jU[indexkj];
301 
302  }
303  else
304  {
305  if (j<jkj)
306  {
307  indexj++;
308  j=BaseType::jL[indexj];
309  }
310  else
311  {
312  indexkj++;
313  jkj=BaseType::jU[indexkj];
314  }
315  }
316  }
317 
318  indexj = BaseType::iU[i]; // traverses row i of BaseType::U
319  indexjlim = BaseType::iU[i+1];
320  j = BaseType::jU[indexj];
321  while ( (indexkj<indexkjlim) && (indexj<indexjlim) )
322  {
323  if (j==jkj)
324  {
325  BaseType::U[indexj]= BaseType::U[indexj]-aik*BaseType::U[indexkj];
326  indexj++;
327  j=BaseType::jU[indexj];
328  indexkj++;
329  jkj=BaseType::jU[indexkj];
330  }
331  else
332  {
333  if (j<jkj)
334  {
335  indexj++;
336  j=BaseType::jU[indexj];
337  }
338  else
339  {
340  indexkj++;
341  jkj=BaseType::jU[indexkj];
342  }
343  }
344  }
345  }
346  }
347 
348  // and that's it...
349  // for debugging only; write out matrices BaseType::L, D, BaseType::U
350  /* std::cout << "BaseType::L, BaseType::U:\n"; */
351  /* for (i=0; i<n; i++) { */
352  /* for (indexj=BaseType::iL[i]; indexj<BaseType::iL[i+1]; indexj++) { */
353  /* j=BaseType::jL[indexj]; */
354  /* std::cout << "BaseType::L[" << i << "," << j << "]=" << BaseType::L[indexj] << "\n"; */
355  /* } */
356  /* } */
357  /* for (i=0; i<n; i++) { */
358  /* for (indexj=BaseType::iU[i]; indexj<BaseType::iU[i+1]; indexj++) { */
359  /* j=BaseType::jU[indexj]; */
360  /* std::cout << "BaseType::U[" << i << "," << j << "]=" << BaseType::U[indexj] << "\n"; */
361  /* } */
362  /* } */
363 
364 
365 
366  for (i=0; i<n; i++) if (BaseType::U[BaseType::iU[i]]==0.00)
367  {
368  KRATOS_THROW_ERROR(std::runtime_error, "Zero in BaseType::U diagonal found!!", "")
369  }
370  }
371 
372 
373 
374 
378 
379 
383 
384 
388 
390  std::string Info() const override
391  {
392  return "ILU0Preconditioner";
393  }
394 
395 
397  void PrintInfo(std::ostream& OStream) const override
398  {
399  OStream << "ILU0Preconditioner";
400  }
401 
402 
403  void PrintData(std::ostream& OStream) const override
404  {
405  }
406 
407 
408 
412 
413 
415 
416 protected:
419 
420 
424 
425 
429 
430 
434 
435 
439 
440 
444 
445 
449 
450 
452 
453 private:
456 
457 
461 
462 
466 
467 
471 
472 
476 
477 
481 
482 
486 
487 
489 
490 }; // Class ILU0Preconditioner
491 
493 
494 
496 
499 
500 
504 
505 
507 template<class TSparseSpaceType, class TDenseSpaceType>
508 inline std::istream& operator >> (std::istream& IStream,
510 {
511  return IStream;
512 }
513 
514 
516 template<class TSparseSpaceType, class TDenseSpaceType>
517 inline std::ostream& operator << (std::ostream& OStream,
519 {
520  rThis.PrintInfo(OStream);
521  OStream << std::endl;
522  rThis.PrintData(OStream);
523 
524 
525  return OStream;
526 }
528 
529 
530 } // namespace Kratos.
531 
532 
533 #endif // KRATOS_ILU0_PRECONDITIONER_H_INCLUDED defined
534 
ILU0Preconditioner class.
Definition: ilu0_preconditioner.h:55
ILUPreconditioner< TSparseSpaceType, TDenseSpaceType > BaseType
Definition: ilu0_preconditioner.h:63
TSparseSpaceType::VectorType VectorType
Definition: ilu0_preconditioner.h:68
TDenseSpaceType::MatrixType DenseMatrixType
Definition: ilu0_preconditioner.h:70
void Initialize(SparseMatrixType &rA, VectorType &rX, VectorType &rB) override
Definition: ilu0_preconditioner.h:132
KRATOS_CLASS_POINTER_DEFINITION(ILU0Preconditioner)
Counted pointer of ILU0Preconditioner.
ILU0Preconditioner()
Default constructor.
Definition: ilu0_preconditioner.h:78
void PrintData(std::ostream &OStream) const override
Print object's data.
Definition: ilu0_preconditioner.h:403
TSparseSpaceType::MatrixType SparseMatrixType
Definition: ilu0_preconditioner.h:66
~ILU0Preconditioner() override
Copy constructor.
Definition: ilu0_preconditioner.h:90
std::string Info() const override
Return information about this object.
Definition: ilu0_preconditioner.h:390
void PrintInfo(std::ostream &OStream) const override
Print information about this object.
Definition: ilu0_preconditioner.h:397
ILUPreconditioner class.
Definition: ilu_preconditioner.h:54
double * L
Definition: ilu_preconditioner.h:280
int * iL
Definition: ilu_preconditioner.h:279
double * U
Definition: ilu_preconditioner.h:280
unsigned int mILUSize
Definition: ilu_preconditioner.h:278
int * jU
Definition: ilu_preconditioner.h:279
int * jL
Definition: ilu_preconditioner.h:279
int * iU
Definition: ilu_preconditioner.h:279
#define KRATOS_THROW_ERROR(ExceptionType, ErrorMessage, MoreInfo)
Definition: define.h:77
end
Definition: DEM_benchmarks.py:180
Vector VectorType
Definition: geometrical_transformation_utilities.h:56
Matrix MatrixType
Definition: geometrical_transformation_utilities.h:55
TSpaceType::IndexType Size(TSpaceType &dummy, typename TSpaceType::VectorType const &rV)
Definition: add_strategies_to_python.cpp:111
REF: G. R. Cowper, GAUSSIAN QUADRATURE FORMULAS FOR TRIANGLES.
Definition: mesh_condition.cpp:21
std::istream & operator>>(std::istream &rIStream, LinearMasterSlaveConstraint &rThis)
input stream function
std::ostream & operator<<(std::ostream &rOStream, const LinearMasterSlaveConstraint &rThis)
output stream function
Definition: linear_master_slave_constraint.h:432
int n
manufactured solution and derivatives (u=0 at z=0 dudz=0 at z=domain_height)
Definition: ode_solve.py:402
int k
Definition: quadrature.py:595
int j
Definition: quadrature.py:648
integer i
Definition: TensorModule.f:17