/[ascend]/trunk/ascend4/solver/model_reorder.h
ViewVC logotype

Annotation of /trunk/ascend4/solver/model_reorder.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (hide annotations) (download) (as text)
Fri Oct 29 20:54:12 2004 UTC (17 years, 8 months ago) by aw0a
File MIME type: text/x-chdr
File size: 8907 byte(s)
Setting up web subdirectory in repository
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_ */

john.pye@anu.edu.au
ViewVC Help
Powered by ViewVC 1.1.22