Changeset 1947
- Timestamp:
- Oct 17, 2005, 4:41:38 PM (19 years ago)
- Location:
- inundation/wiki
- Files:
-
- 1 edited
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
inundation/wiki/least_squares_redesign.txt
r1932 r1947 6 6 7 7 Software, called least squares, has been developed to implement a 8 penalised least-squares fit and associated interpolations. It is in 9 least_squares.py. Steven Roberts outlined the least squares algorithm 10 used. The code is currently not meeting user requirements with 11 regards to speed and memory use. Additional functionality is also needed. 8 penalised least-squares fit and associated interpolations. It is 9 currently in least_squares.py. Steven Roberts outlined the least 10 squares algorithm used. The code is currently not meeting user 11 requirements with regards to speed and memory use. Additional 12 functionality is also needed. 13 12 14 13 15 SCOPE 14 This is looking at refactoring the Class Interpolation and the 15 functions fit_to_mesh_file, fit_to_mesh and the command line use of 16 least_squares.py. 16 17 This is looking at redesigning the least_squares module, excluding 18 interpolate_function and pts2rectangle. (Other modules will 19 be modified, based on these changes.) 20 17 21 18 22 LIFE-CYCLE … … 34 38 INTRODUCTION 35 39 36 This document specifies the requirements to implement least squares 37 is refactored. 40 This document specifies the requirements of the refactoring of least squares. 38 41 39 42 DEFINITIONS … … 49 52 50 53 51 Requirements 54 Requirements - Fitting 52 55 53 When interpolating, return information on which points were outside 54 the mesh (in such a way that it can not be interporated as real data). 55 If attribute information for points outside the mesh is returned, that can 56 only be a float, let the user set the default value that is returned 57 for points outside the mesh. 56 When in verbose mode display how many points are in the 57 mesh and how many are outside its boundary. Also display the max # of 58 points/ triangle and the minimum number of points. If this operation 59 takes a lot of time, let it be optional. 58 60 59 When fitting, when in verbose mode display how many triangles are in the 60 mesh and how many are out. Also display the max # of points/ triangle 61 and the minimum number of points. If this operation takes alot of 62 time, let it be optional. 63 64 Warn the user when fitting to mesh if the mesh is outside the points boundary. 65 (Note: by using alpha least squares can always return a result in this 66 situation) 61 Raise an exception if no points are inside the mesh. 67 62 68 63 Fitting 5 million points to a one million triangles mesh will not cause a 69 64 memory error. 70 65 66 Remove least_squares commandline interface. 67 68 Points do not have to be supplied all at once. They can be supplied 69 as blocks. (This will improve memory use) 70 71 Requirements - Interpolation 72 73 Return information on which points were outside the mesh (in such a 74 way that it can not be interpreted as real data). If attribute 75 information for points outside the mesh is returned, that can only be 76 a float, let the user set the default value that is returned for 77 points outside the mesh. 78 71 79 Reduce the time spent building matrix A. (not a testable requirement) 72 80 73 (This isn't long, are there any other requirements?)74 75 Requirement Notes76 How should we handle points outside of the mesh when interpolating?77 Currently the interpolated values are set to 0.0.78 Other options are, set to a given value.79 Raise an error.80 Raise/return a warning and set to a given value/0.0. (I like this one)81 81 82 Points do not have to be supplied all at once. They can be supplied 83 as blocks. (This will improve memory use) 82 84 83 How should interpolate_sww respond? 84 warning/error/exit/replace with given value. 85 A target to aim for 86 Algorithmic complexity of build equations should be linear in number 87 of data points and logorithmic in the number of vertices. 88 89 Constraint 90 Memory consumption of least squares equations must be indepenent on 91 the number of datapoints. (Except for the memory used to store the points.) 92 93 How should interpolate_sww respond to a ? 94 Warning and replace with given value. 85 95 86 96 General Error Handling Guidelines … … 115 125 *To save memory; 116 126 When interpolating, don't build AtA, B and D. (This has been implemented) 117 When fitting, don't build A. - Work with AtA and Atz. 127 When fitting, don't build A. - Work with AtA and Atz. Build Atz 128 directly, rather than through At*z - use code similar to AtA 118 129 119 130 … … 124 135 This is for the layer interpolation and fitting with IO: Use blocking 125 136 when interpolating/fitting a large number of points (how large? Can the 126 program check the available memory and work out a good block size?) 137 program check the available memory and work out a good block size? 138 Maybe have it user specified. Do have the option for user specified) 127 139 128 The code has to be refactored so fitting can handl ingblocked point140 The code has to be refactored so fitting can handle blocked point 129 141 info. Need a building phase and a solve phase. 130 142 … … 137 149 Options (still thinking about this one) 138 150 * It should look in the cell of the point and then all adjacent 139 cells. If it isn't there then ... we have problems. My feeling is it 140 has to be there. 141 - Building the structure to keep this info could be prohibative. 151 cells. If it isn't there then ... expand more. 152 - Building the structure to keep this info could be prohibitive. 142 153 154 *A feature that could work for the current implementation is to keep a 155 list of triangles that have been checked, so each incorrect triangle 156 isn't checked three times, if all three verts are in the cell being checked. 143 157 144 158 Another speed up option is to write the bottlenecks in C. Do it if necessary. 145 159 160 * To give warnings. 161 Use warnings module? Check this out. 146 162 147 163 DESIGN IDEAS, refactoring … … 156 172 157 173 Have least squares as two stand alone packages. One that has the guts 158 of LS (e.g. the two new classes). One that ishas the IO API's159 (functions that load and write files ). The guts package will be160 dependent of the general mesh package. The IO API will rely on an IO 161 module.174 of LS (e.g. the two new classes). One that has the IO API's 175 (functions that load and write files and do the blocking). The guts 176 package will be dependent of the general mesh package. The IO API 177 will rely on an IO module. 162 178 163 179 HOW WILL IMPLEMENTATION OCCUR? … … 165 181 and paste from the old least squares. Implement memory and time tests 166 182 on the old least squares (and new LS) before doing any changes. 183 184 For the speed up, discuss/ get go ahead from Ole before implementing 185 any major changes, since there is no obvious way forward.
Note: See TracChangeset
for help on using the changeset viewer.