43 #include "Ifpack_ConfigDefs.h"
44 #include "Ifpack_Partitioner.h"
45 #include "Ifpack_OverlappingPartitioner.h"
46 #include "Ifpack_LinePartitioner.h"
47 #include "Ifpack_Graph.h"
48 #include "Epetra_Util.h"
53 inline double compute_distance_coordinates(
double x0,
double y0,
double z0,
int nn,
const double*xvals,
const double*yvals,
const double*zvals) {
55 if(xvals) mydist += (x0 - xvals[nn]) * (x0 - xvals[nn]);
56 if(yvals) mydist += (y0 - yvals[nn]) * (y0 - yvals[nn]);
57 if(zvals) mydist += (z0 - zvals[nn]) * (z0 - zvals[nn]);
61 inline double compute_distance_matrix_entries(
const double *vals,
int id,
int NumEqns) {
63 for(
int i=0; i<NumEqns; i++)
64 sum+=std::abs(vals[
id+i]);
70 inline void Ifpack_LinePartitioner::local_automatic_line_search(
int NumEqns,
int * blockIndices,
int last,
int next,
int LineID,
double tol,
int *itemp,
double * dtemp)
const {
71 double *xvals=xcoord_, *yvals=ycoord_, *zvals=zcoord_;
77 int * indices = &itemp[allocated_space];
78 double * merit= dtemp;
79 double * vals = &dtemp[allocated_space];
81 while (blockIndices[next] == -1) {
84 int neighbors_in_line=0;
86 if(mode_==MATRIX_ENTRIES) Matrix_->
ExtractMyRowCopy(next,allocated_space,n,vals,cols);
90 double x0 = (xvals) ? xvals[next/NumEqns] : 0.0;
91 double y0 = (yvals) ? yvals[next/NumEqns] : 0.0;
92 double z0 = (zvals) ? zvals[next/NumEqns] : 0.0;
96 for(
int i=0; i<n; i+=NumEqns) {
97 if(cols[i] >=N)
continue;
98 int nn = cols[i] / NumEqns;
99 if(blockIndices[nn]==LineID) neighbors_in_line++;
100 if(mode_==COORDINATES) merit[neighbor_len] = compute_distance_coordinates(x0,y0,z0,nn,xvals,yvals,zvals);
102 merit[neighbor_len] = - compute_distance_matrix_entries(vals,i,NumEqns);
104 if(cols[i]==next) merit[neighbor_len] = -DBL_MAX;
107 indices[neighbor_len]=cols[i];
112 if(neighbors_in_line > 1)
break;
115 for(
int k=0; k<NumEqns; k++)
116 blockIndices[next + k] = LineID;
121 if(neighbor_len > 2 && indices[1] != last && blockIndices[indices[1]] == -1 && merit[1] < tol*merit[neighbor_len-1]) {
125 else if(neighbor_len > 3 && indices[2] != last && blockIndices[indices[2]] == -1 && merit[2] < tol*merit[neighbor_len-1]) {
137 int Ifpack_LinePartitioner::Compute_Blocks_AutoLine(
int * blockIndices)
const {
138 double *xvals=xcoord_, *yvals=ycoord_, *zvals=zcoord_;
139 int NumEqns = NumEqns_;
140 double tol = threshold_;
144 int * cols =
new int[2*allocated_space];
145 int * indices = &cols[allocated_space];
146 double * merit =
new double[2*allocated_space];
147 double * vals = &merit[allocated_space];
149 int * itemp =
new int[2*allocated_space];
150 double *dtemp =
new double[2*allocated_space];
155 for(
int i=0; i<N; i+=NumEqns) {
158 if(blockIndices[i] !=-1)
continue;
161 if(mode_==MATRIX_ENTRIES) Matrix_->
ExtractMyRowCopy(i,allocated_space,nz,vals,cols);
164 double x0 = (xvals) ? xvals[i/NumEqns] : 0.0;
165 double y0 = (yvals) ? yvals[i/NumEqns] : 0.0;
166 double z0 = (zvals) ? zvals[i/NumEqns] : 0.0;
169 for(
int j=0; j<nz; j+=NumEqns) {
170 int nn = cols[j] / NumEqns;
171 if(cols[j] >=N)
continue;
172 if(mode_==COORDINATES) merit[neighbor_len] = compute_distance_coordinates(x0,y0,z0,nn,xvals,yvals,zvals);
174 merit[neighbor_len] = - compute_distance_matrix_entries(vals,j,NumEqns);
176 if(cols[j]==i) merit[neighbor_len] = -DBL_MAX;
178 indices[neighbor_len] = cols[j];
185 for(
int k=0; k<NumEqns; k++)
186 blockIndices[i + k] = num_lines;
189 if(neighbor_len > 2 && merit[1] < tol*merit[neighbor_len-1]) {
190 local_automatic_line_search(NumEqns,blockIndices,i,indices[1],num_lines,tol,itemp,dtemp);
193 if(neighbor_len > 3 && merit[2] < tol*merit[neighbor_len-1]) {
194 local_automatic_line_search(NumEqns,blockIndices,i,indices[2],num_lines,tol,itemp,dtemp);
212 if(mode_==COORDINATES && !xcoord_ && !ycoord_ && !zcoord_) IFPACK_CHK_ERR(-1);
virtual int ExtractMyRowCopy(int MyRow, int LenOfIndices, int &NumIndices, int *Indices) const =0
Extracts a copy of input local row.
int MaxNumEntries() const
Returns the max number of local entries in a row.
int NumMyRows() const
Returns the number of local rows.
std::vector< int > Partition_
Partition_[i] contains the ID of non-overlapping part it belongs to.
int ComputePartitions()
Computes the partitions. Returns 0 if successful.
static void Sort(bool SortAscending, int NumKeys, T *Keys, int NumDoubleCompanions, double **DoubleCompanions, int NumIntCompanions, int **IntCompanions, int NumLongLongCompanions, long long **LongLongCompanions)
const Ifpack_Graph * Graph_
Reference to the graph to be partitioned.
int NumLocalParts_
Number of local subgraphs.
virtual int ExtractMyRowCopy(int MyRow, int Length, int &NumEntries, double *Values, int *Indices) const =0
std::vector< std::vector< int > > Parts_
Parts_[i][j] is the ID of the j-th row contained in the (overlapping)