home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / numanal / 2676 < prev    next >
Encoding:
Internet Message Format  |  1992-09-10  |  2.7 KB
  1. Xref: sparky sci.math.num-analysis:2676 sci.math.symbolic:2367
  2. Newsgroups: sci.math.num-analysis,sci.math.symbolic
  3. Path: sparky!uunet!mcsun!Germany.EU.net!infko!inews
  4. From: berling@infko.uni-koblenz.de
  5. Subject: decomposing sets of equations
  6. Message-ID: <1992Sep10.131427.22221@infko.uucp>
  7. Sender: inews@infko.uucp (inews)
  8. Organization: University of Koblenz, Germany
  9. Date: Thu, 10 Sep 1992 13:14:27 GMT
  10. Lines: 53
  11.  
  12. Hello!
  13.  
  14. I have some questions concerning methods for solving large sets 
  15. of mostly nonlinear equations (it's a kind of constraint solving problem).
  16.  
  17. I am seeking for methods to decompose a possible large set of
  18. equations into sets of smaller ones which have to be solved
  19. simultaneously in a certain order. Using a bipartite graph with 
  20. vertices representing the equations and variables 
  21. and undirected arcs representing
  22. the "belongs-to" relationship, one may use a maximum-matching algorithm
  23. to determine a partition into smaller sets. My question is, are there
  24. any other techniques, especially techniques which allow a better 
  25. control of the quality of the generated partition (e.g. number of sets of
  26. more than one equation is minimal)?
  27.  
  28. Having a set of equations which have to be solved simultaneously, I am
  29. further interested in methods for eliminating as much variables as
  30. possible before solving it using Newton-Raphson iteration. Having for
  31. example a set of 4 equations determining the variables a, b, c, d:
  32.  
  33.     1. a = f (c, d)
  34.     2. b = g (a, c)
  35.     3. c = h (d)
  36.     4. d = i (b)
  37.  
  38. the system is reducible to the equation:
  39.  
  40.     b = g (f (h (i (b)), i (b)), h (i (b)))
  41. or
  42.     d = i (g (f (h (d), d), h (d)))
  43.  
  44. which may be easier to solve using Newton-Raphson. Knowing wich equation 
  45. has to be solved for which variable, the problem has probably something
  46. to do with finding the feedback vertices in strong components of
  47. directed graphs, a problem known to be NP-complete. Again, my question is
  48. are there any other techniques or heuristics which solve this problem
  49. or special cases perhaps more efficient?
  50.  
  51. I will thank you for any hints!
  52.  
  53. +----------------------------+-----------------------------------------+
  54. |                            |                                         |
  55. |  Roland Berling            |  Tel.:   +49 261 9119 436               |
  56. |  Universit"at Koblenz      |  Fax.:   +49 261 9119 499               |
  57. |  Institut f"ur Informatik  |  e-mail: berling@infko.uni-koblenz.de   |
  58. |  Rheinau 3-4               |                                         |
  59. |  D-5400 Koblenz            |                                         |
  60. |  Germany                   |                                         |
  61. |                            |                                         |
  62. +----------------------------+-----------------------------------------+
  63.  
  64.  
  65.