home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10656 < prev    next >
Encoding:
Text File  |  1992-08-27  |  3.0 KB  |  67 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!nwnexus!amc-gw!kenb
  3. From: kenb@amc.com (Ken Birdwell)
  4. Subject: Triangular systems of equations.
  5. Message-ID: <1992Aug28.002556.7374@amc.com>
  6. Organization: Applied Microsystems Corporation
  7. Date: Fri, 28 Aug 1992 00:25:56 GMT
  8. Lines: 57
  9.  
  10. I'm looking for a method to help me solve large systems of 
  11. simultanious equations (10,000+) that are related to one another in 
  12. the form of an irregular triangular mesh.  My problem seems to be in 
  13. not being able to order the points into a tight enough diagonal 
  14. sparse matrix.  If you know of any references on solving systems 
  15. like this, please forward them.
  16.  
  17.  
  18. The problem:
  19.     Given an irregular non-overlapping 2D open triangular mesh of a N 
  20.     points, with known coordinates for all edge points,  calculate "good" 
  21.     coordinates for all the interior points while maintaining the feature of 
  22.     non-overlapping triangles.  
  23.  
  24. My solution so far:
  25.     Cycle through all the interior points, calculating for each one a new 
  26.     coordinate by averaging the coordinates of all of its 'mesh' neighbors.
  27.     Repeat until the points stop moving (much).
  28.     
  29.     I've also added the feature that all the points are weighted by 
  30.     how well their new triangles match the surface area of their 
  31.     original triangles.  This kinda forces a equal area distortion, which 
  32.     is desirable.
  33.  
  34.     The problem is that it takes N*sqr(N) time for the interitive approach
  35.     to settle down into a solution. When N > 10k, this is a problem, and 
  36.     can take over a 1/2 hour and a 486/33.
  37.  
  38. What I tried to do:
  39.     Well, I tried to build this into a very large system of system of 
  40.     simultanions equations, and interate through it one or two times until 
  41.     I could calculate what weights to use.  
  42.     
  43.     I wrote some software that does sparse matrices (zero's take up no 
  44.     memory), and got this solution to work fine for systems with around 
  45.     2,000 points. It also has very nice linear computational cost (about 30 
  46.     seconds per 1000 points).   With systems larger then about 10,000, the 
  47.     sparse matrix starts to fill up (I'm using Gaussian elimination with 
  48.     back subsitution). Systems any larger start to take up alot more memory, 
  49.     and pretty soon fill up my 32MB of RAM.
  50.  
  51.     The problem, I think, is that I don't have a good way to order the 
  52.     points in the matrix so that connected points keep a tight enough 
  53.     diagonal.  What I do now is to pick a single starting point, and 
  54.     interate outward from that point, numbering each point as they get 
  55.     farther and farther away from the starting point.  This creates (in the 
  56.     matrix) what look like a central band with two other parallel bands, one 
  57.     on each side of the central band, that bow out in the middle. This 
  58.     bowing in the middle ends up causing the matrix to fill up with non-zero 
  59.     values, and also killing performance.
  60.  
  61.     Any method that will order the points better, or a way to swap rows and 
  62.     columns to minimize the memory used would be much appreciated.
  63.     
  64.  
  65. -- 
  66.  
  67.