ascend4/solver/model_reorder.h

/*
 *  Model-based Reordering Routines
 *  by Benjamin Andrew Allan
 *  6/22/96
 *  Version: $Revision: 1.5 $
 *  Version control file: $RCSfile: model_reorder.h,v $
 *  Date last modified: $Date: 1997/07/18 12:14:44 $
 *  Last modified by: $Author: mthomas $
 *  Copyright(C) 1996 Benjamin Andrew Allan
 *
 *  This file is part of the ASCEND IV math programming system.
 *  These functions are part of a new design for feeding
 *  solvers from the ASCEND compiler.
 *
 *  File to play MODEL-relation based reordering games.
 *  We're starting with a basic RBBD implementation.
 *  Assumptions:
 *  - If the MODELs are hierarchical, then they have been indexed in a
 *  tree bottom-up fashion.
 *  - Input is a square block that needs tearing and not a rectangle.
 *
 *  The ASCEND IV math programming system is free software; you can redistribute
 *  it and/or modify it under the terms of the GNU General Public License as
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version.
 *
 *  The ASCEND IV math programming system is distributed in hope that it will be
 *  useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along with
 *  the program; if not, write to the Free Software Foundation, Inc., 675
 *  Mass Ave, Cambridge, MA 02139 USA.  Check the file named COPYING.
 *  COPYING is found in ../compiler.
 */
#ifndef _model_reorder_h_seen_
#define _model_reorder_h_seen_
/* requires #include "base.h" */
/* requires #include "slv_types.h" */
/* requires #include "mtx.h" */

#define MRDEBUG 0
 /* if !=0, generate spew while working */
#define CUTOFFDEFAULT 1000
 /* tuning parameter in need of investigation */

typedef struct mr_bisection_structure {
  /* data spaces */
  slv_system_t slv;
  mtx_matrix_t mtx;
  int32 *local;     /* MODEL indexed array of counts of relations */
  char *active;     /* in block flags for models */
  int32 *tmpmodlist;    /* a unique list of indices of models found so far */
  int32 tmpmodused; /* currently used length of tmpmodlist */
  int32 activelen;  /* length of active,local and tmpmodlist arrays */

  /* control parameters */
  int32 cutoff;
  int32 maxtears;
  double maxtearfraction;

  /* miscellaneous statistics */
  int32 ntears;
  int32 nblts;
} mr_reorder_t;
/************************************************************************\
  The mr_reorder_t is a workspace structure containing most of the items
  needed for the recursive function mr_bisect_partition and any similar
  functions. mr_reorder_create and destroy are provided to set up
  a mr_reorder_t.
- The mtx herein should correspond to the solvers_rel/var lists of the
  slv_system_t here. 
- The pointers local, tmpmodlist, and active should contain arrays of
  size activelen and these arrays should be (re)initialized to 0
  for each call of mr_bisect_partition.
- Activelen should be the number of models in the slv_system_t. In
  particular array[rel_model(rel)] should exist for all rel in the
  solvers_rel_list.
- Cutoff is the smallest block the user wants us to try to tear.
- Maxtears is the largest number of tears user wants to allow in any
  single block. IT IS IGNORED.
- Maxtearfraction is the largest percentage of any single block the
  user wants us to try to tear. IT IS IGNORED.
- Ntears is the number of tear columns we find.
- Nblts is the number of BLT permutations we do.
\************************************************************************/

extern mr_reorder_t *mr_reorder_create(slv_system_t, mtx_matrix_t, int32);
/************************************************************************\
mrsys = mr_reorder_create(slvsys,mtx,nmodels);
Returns a mr_reorder_t all set up with cutoff set to CUTOFFDEFAULT
for a problem that has nmodels models in it. 
The arrays are initialized to 0.
rel_model(rel) of any rel in slvsys should return a number 0..nmodels-1.
Returns NULL if insufficient memory.
\************************************************************************/

extern void mr_reorder_destroy(mr_reorder_t *);
/************************************************************************\
mr_reorder_destroy(mrsys);
Deallocate a mr_reorder_t *.
\************************************************************************/

typedef int (MRBlockReorderF)(slv_system_t,mtx_matrix_t,mtx_region_t *);
/************************************************************************\
This is a user supplied function that will be applied called
with sys->slv,sys->mtx, and regions that fall below sys->cutoff
in size.  The user may do any sort of logic they care to,
including ignoring reordering blocks below a certain size. It
must be supplied, even if it does nothing.

This function could be dumb and just apply SPK1-like things, or
be very smart and reorder based on the number and type of models
found in the region. This function should be the subject of some
experimentation since mr_bisect_partition just identifies tears
and subregions.

This function is also the one called on blocks bigger than the
cutoff size that however contain equations from exactly 1 MODEL.

We don't (yet, anyway) check the return value.
\************************************************************************/

extern int mr_bisect_partition(mr_reorder_t *, mtx_region_t *, int,
                               MRBlockReorderF);
/************************************************************************\
stat = mr_bisect_partition(sys, reg, top, rfunc);
mr_reorder_t *sys;
mtx_region_t *reg;
int top;
MRBlockReorderF rfunc;

This function is recursive and produces a sys->mtx reordered to be
recursive block bordered diagonal (RBBD).

If top is 1, the region given in block should be (within itself)
a strongly connected square block. If top is 0, we will do a BLT
permutation on the region first assuming the region is square
and has a full diagonal. The normal mode of externally calling
this function should be with top==1 and we then recurse with
top==0.

One the outermost call, the relations in reg should have all
their REL_TORN flag bits set to 0.  On return from the outermost
call, the columns identified as tears will have the REL_TORN
flag bits set to 1. It turns out we don't use the REL_PARTITION
flag.

The mr_reorder_t * given must be filled in completely before
calling this function. Anything amiss will cause us to return
immediately without doing anything.  Returns 0 if ok, > 0 if
anything else wrong. Basically, the only thing that can go
wrong is, if during one of our blt permutations, we run out
of memory. Nonzero return value will be the number of times
we encountered malloc failure.

The values in reg may be messed with, so if the data in
reg is needed after this function call, keep it elsewhere.
\************************************************************************/

extern int mr_bisect_partition2(mr_reorder_t *, mtx_region_t *, int,
                               MRBlockReorderF);
/************************************************************************\
stat = mr_bisect_partition2(sys, reg, top, rfunc);
mr_reorder_t *sys;
mtx_region_t *reg;
int top;
MRBlockReorderF rfunc;

This is the function most similar to the algorithm described/tested
in the Abbott thesis.

This function is recursive and produces a sys->mtx reordered to be
recursive block bordered diagonal (RBBD) with borders roughly twice
the size of those in mr_bisect_partition because of a simple idiocy
in the way it locates tears. The relative performance of the two
versions is not clear.

If top is 1, the region given in block should be (within itself)
a strongly connected square block. If top is 0, we will do a BLT
permutation on the region first assuming the region is square
and has a full diagonal. The normal mode of externally calling
this function should be with top==1 and we then recurse with
top==0.

One the outermost call, the relations in reg should have all
their REL_TORN flag bits set to 0.  On return from the outermost
call, the columns identified as tears will have the REL_TORN
flag bits set to 1. It turns out we don't use the REL_PARTITION
flag.

The mr_reorder_t * given must be filled in completely before
calling this function. Anything amiss will cause us to return
immediately without doing anything.  Returns 0 if ok, > 0 if
anything else wrong. Basically, the only thing that can go
wrong is, if during one of our blt permutations, we run out
of memory. Nonzero return value will be the number of times
we encountered malloc failure.

The values in reg may be messed with, so if the data in
reg is needed after this function call, keep it elsewhere.
\************************************************************************/
#endif /* _model_reorder_h_seen_ */
1	aw0a	1	/*
2			* Model-based Reordering Routines
3			* by Benjamin Andrew Allan
4			* 6/22/96
5			* Version: $Revision: 1.5 $
6			* Version control file: $RCSfile: model_reorder.h,v $
7			* Date last modified: $Date: 1997/07/18 12:14:44 $
8			* Last modified by: $Author: mthomas $
9			* Copyright(C) 1996 Benjamin Andrew Allan
10			*
11			* This file is part of the ASCEND IV math programming system.
12			* These functions are part of a new design for feeding
13			* solvers from the ASCEND compiler.
14			*
15			* File to play MODEL-relation based reordering games.
16			* We're starting with a basic RBBD implementation.
17			* Assumptions:
18			* - If the MODELs are hierarchical, then they have been indexed in a
19			* tree bottom-up fashion.
20			* - Input is a square block that needs tearing and not a rectangle.
21			*
22			* The ASCEND IV math programming system is free software; you can redistribute
23			* it and/or modify it under the terms of the GNU General Public License as
24			* published by the Free Software Foundation; either version 2 of the
25			* License, or (at your option) any later version.
26			*
27			* The ASCEND IV math programming system is distributed in hope that it will be
28			* useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
29			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
30			* General Public License for more details.
31			*
32			* You should have received a copy of the GNU General Public License along with
33			* the program; if not, write to the Free Software Foundation, Inc., 675
34			* Mass Ave, Cambridge, MA 02139 USA. Check the file named COPYING.
35			* COPYING is found in ../compiler.
36			*/
37			#ifndef _model_reorder_h_seen_
38			#define _model_reorder_h_seen_
39			/* requires #include "base.h" */
40			/* requires #include "slv_types.h" */
41			/* requires #include "mtx.h" */
42
43			#define MRDEBUG 0
44			/* if !=0, generate spew while working */
45			#define CUTOFFDEFAULT 1000
46			/* tuning parameter in need of investigation */
47
48			typedef struct mr_bisection_structure {
49			/* data spaces */
50			slv_system_t slv;
51			mtx_matrix_t mtx;
52			int32 local; / MODEL indexed array of counts of relations */
53			char active; / in block flags for models */
54			int32 tmpmodlist; / a unique list of indices of models found so far */
55			int32 tmpmodused; /* currently used length of tmpmodlist */
56			int32 activelen; /* length of active,local and tmpmodlist arrays */
57
58			/* control parameters */
59			int32 cutoff;
60			int32 maxtears;
61			double maxtearfraction;
62
63			/* miscellaneous statistics */
64			int32 ntears;
65			int32 nblts;
66			} mr_reorder_t;
67			/************************************************************************\
68			The mr_reorder_t is a workspace structure containing most of the items
69			needed for the recursive function mr_bisect_partition and any similar
70			functions. mr_reorder_create and destroy are provided to set up
71			a mr_reorder_t.
72			- The mtx herein should correspond to the solvers_rel/var lists of the
73			slv_system_t here.
74			- The pointers local, tmpmodlist, and active should contain arrays of
75			size activelen and these arrays should be (re)initialized to 0
76			for each call of mr_bisect_partition.
77			- Activelen should be the number of models in the slv_system_t. In
78			particular array[rel_model(rel)] should exist for all rel in the
79			solvers_rel_list.
80			- Cutoff is the smallest block the user wants us to try to tear.
81			- Maxtears is the largest number of tears user wants to allow in any
82			single block. IT IS IGNORED.
83			- Maxtearfraction is the largest percentage of any single block the
84			user wants us to try to tear. IT IS IGNORED.
85			- Ntears is the number of tear columns we find.
86			- Nblts is the number of BLT permutations we do.
87			\************************************************************************/
88
89			extern mr_reorder_t *mr_reorder_create(slv_system_t, mtx_matrix_t, int32);
90			/************************************************************************\
91			mrsys = mr_reorder_create(slvsys,mtx,nmodels);
92			Returns a mr_reorder_t all set up with cutoff set to CUTOFFDEFAULT
93			for a problem that has nmodels models in it.
94			The arrays are initialized to 0.
95			rel_model(rel) of any rel in slvsys should return a number 0..nmodels-1.
96			Returns NULL if insufficient memory.
97			\************************************************************************/
98
99			extern void mr_reorder_destroy(mr_reorder_t *);
100			/************************************************************************\
101			mr_reorder_destroy(mrsys);
102			Deallocate a mr_reorder_t *.
103			\************************************************************************/
104
105			typedef int (MRBlockReorderF)(slv_system_t,mtx_matrix_t,mtx_region_t *);
106			/************************************************************************\
107			This is a user supplied function that will be applied called
108			with sys->slv,sys->mtx, and regions that fall below sys->cutoff
109			in size. The user may do any sort of logic they care to,
110			including ignoring reordering blocks below a certain size. It
111			must be supplied, even if it does nothing.
112
113			This function could be dumb and just apply SPK1-like things, or
114			be very smart and reorder based on the number and type of models
115			found in the region. This function should be the subject of some
116			experimentation since mr_bisect_partition just identifies tears
117			and subregions.
118
119			This function is also the one called on blocks bigger than the
120			cutoff size that however contain equations from exactly 1 MODEL.
121
122			We don't (yet, anyway) check the return value.
123			\************************************************************************/
124
125			extern int mr_bisect_partition(mr_reorder_t , mtx_region_t , int,
126			MRBlockReorderF);
127			/************************************************************************\
128			stat = mr_bisect_partition(sys, reg, top, rfunc);
129			mr_reorder_t *sys;
130			mtx_region_t *reg;
131			int top;
132			MRBlockReorderF rfunc;
133
134			This function is recursive and produces a sys->mtx reordered to be
135			recursive block bordered diagonal (RBBD).
136
137			If top is 1, the region given in block should be (within itself)
138			a strongly connected square block. If top is 0, we will do a BLT
139			permutation on the region first assuming the region is square
140			and has a full diagonal. The normal mode of externally calling
141			this function should be with top==1 and we then recurse with
142			top==0.
143
144			One the outermost call, the relations in reg should have all
145			their REL_TORN flag bits set to 0. On return from the outermost
146			call, the columns identified as tears will have the REL_TORN
147			flag bits set to 1. It turns out we don't use the REL_PARTITION
148			flag.
149
150			The mr_reorder_t * given must be filled in completely before
151			calling this function. Anything amiss will cause us to return
152			immediately without doing anything. Returns 0 if ok, > 0 if
153			anything else wrong. Basically, the only thing that can go
154			wrong is, if during one of our blt permutations, we run out
155			of memory. Nonzero return value will be the number of times
156			we encountered malloc failure.
157
158			The values in reg may be messed with, so if the data in
159			reg is needed after this function call, keep it elsewhere.
160			\************************************************************************/
161
162			extern int mr_bisect_partition2(mr_reorder_t , mtx_region_t , int,
163			MRBlockReorderF);
164			/************************************************************************\
165			stat = mr_bisect_partition2(sys, reg, top, rfunc);
166			mr_reorder_t *sys;
167			mtx_region_t *reg;
168			int top;
169			MRBlockReorderF rfunc;
170
171			This is the function most similar to the algorithm described/tested
172			in the Abbott thesis.
173
174			This function is recursive and produces a sys->mtx reordered to be
175			recursive block bordered diagonal (RBBD) with borders roughly twice
176			the size of those in mr_bisect_partition because of a simple idiocy
177			in the way it locates tears. The relative performance of the two
178			versions is not clear.
179
180			If top is 1, the region given in block should be (within itself)
181			a strongly connected square block. If top is 0, we will do a BLT
182			permutation on the region first assuming the region is square
183			and has a full diagonal. The normal mode of externally calling
184			this function should be with top==1 and we then recurse with
185			top==0.
186
187			One the outermost call, the relations in reg should have all
188			their REL_TORN flag bits set to 0. On return from the outermost
189			call, the columns identified as tears will have the REL_TORN
190			flag bits set to 1. It turns out we don't use the REL_PARTITION
191			flag.
192
193			The mr_reorder_t * given must be filled in completely before
194			calling this function. Anything amiss will cause us to return
195			immediately without doing anything. Returns 0 if ok, > 0 if
196			anything else wrong. Basically, the only thing that can go
197			wrong is, if during one of our blt permutations, we run out
198			of memory. Nonzero return value will be the number of times
199			we encountered malloc failure.
200
201			The values in reg may be messed with, so if the data in
202			reg is needed after this function call, keep it elsewhere.
203			\************************************************************************/
204			#endif /* _model_reorder_h_seen_ */