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	/*
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_ */