home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10667 < prev    next >
Encoding:
Text File  |  1992-08-29  |  2.6 KB  |  55 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!caen!takriti
  3. From: takriti@engin.umich.edu (samer Takriti)
  4. Subject: Re: Triangular systems of equations.
  5. Message-ID: <a8j-Jq@engin.umich.edu>
  6. Date: Fri, 28 Aug 92 12:03:08 EDT
  7. Organization: University of Michigan Engineering, Ann Arbor
  8. References: <1992Aug28.002556.7374@amc.com>
  9. Nntp-Posting-Host: maize.engin.umich.edu
  10. Lines: 43
  11.  
  12. In article <1992Aug28.002556.7374@amc.com> kenb@amc.com (Ken Birdwell) writes:
  13. >I'm looking for a method to help me solve large systems of 
  14. >simultanious equations (10,000+) that are related to one another in 
  15. >the form of an irregular triangular mesh.  My problem seems to be in 
  16. >not being able to order the points into a tight enough diagonal 
  17. >sparse matrix.  If you know of any references on solving systems 
  18. >like this, please forward them.
  19. >
  20. >
  21. >The problem:
  22. >    Given an irregular non-overlapping 2D open triangular mesh of a N 
  23. >    points, with known coordinates for all edge points,  calculate "good" 
  24. >    coordinates for all the interior points while maintaining the feature of 
  25. >    non-overlapping triangles.  
  26. >
  27. >    The problem, I think, is that I don't have a good way to order the 
  28. >    points in the matrix so that connected points keep a tight enough 
  29. >    diagonal.  What I do now is to pick a single starting point, and 
  30. >    interate outward from that point, numbering each point as they get 
  31. >    farther and farther away from the starting point.  This creates (in the 
  32. >    matrix) what look like a central band with two other parallel bands, one 
  33. >    on each side of the central band, that bow out in the middle. This 
  34. >    bowing in the middle ends up causing the matrix to fill up with non-zero 
  35. >    values, and also killing performance.
  36. >
  37. Are you doing "Surveying" ? If this is the case there is a least
  38. square method that will give you the "best" coordinates by solving
  39. a system of equations. (There is no need for iterations). I worked
  40. on this more than ten years ago and cannot find the name of the 
  41. reference. You should check with civil engineers. The method is
  42. well known. (There are two: direct and indirect but both of them
  43. use least squares).
  44. If you want to "exploit" the structure of your matrix in a better 
  45. way, there is a computer package called sparcepack. It uses graph
  46. theory to minimize the fill-in of the matrices. There is a book 
  47. written by J. K. Reid, E. M. L. Beale and a third Professor about
  48. sparse matrices. You could chec in the Mathematical Programming
  49. journal. For example, there is an article in Math. Programming 24
  50. (1982), pp. 55-69 by Reid: A sparsity-exploiting variant of the
  51. Bartels-Golub Decomposition for Linear Programming. You can start
  52. there.
  53. -Samer
  54.  
  55.