home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / sci / math / numanal / 3567 < prev    next >
Encoding:
Internet Message Format  |  1992-12-14  |  3.8 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!saimiri.primate.wisc.edu!usenet.coe.montana.edu!news.u.washington.edu!ogicse!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!andrew.cmu.edu!al2c+
  2. From: al2c+@andrew.cmu.edu (Anand V. Lakshmikumaran)
  3. Newsgroups: sci.math.num-analysis
  4. Subject: Determinants (contd..)
  5. Message-ID: <Qf==5T200X0F41LLBc@andrew.cmu.edu>
  6. Date: 14 Dec 92 06:07:59 GMT
  7. Article-I.D.: andrew.Qf==5T200X0F41LLBc
  8. References: <Uf_ue8S00X0F01LIFN@andrew.cmu.edu>
  9.     <8f_ul__00X0FM1LIoi@andrew.cmu.edu>
  10. Organization: Doctoral student, Mechanical Engineering, Carnegie Mellon, Pittsburgh, PA
  11. Lines: 87
  12. In-Reply-To: <8f_ul__00X0FM1LIoi@andrew.cmu.edu>
  13.  
  14. Excerpts from netnews.sci.math.num-analysis: 13-Dec-92 Determinants A.
  15. Lakshmikumaran@andrew (1278)
  16.  
  17. > I am interested in an efficient routine to compute the determinant of a matrix
  18. > of size n (n < 100), when only one of the terms of the determinant has been 
  19. > changed; in terms of the determinant of the original matrix.
  20.  
  21. > To make it more clear,
  22.  
  23. > Step 1: I have this matrix G and i need to compute its determinant
  24. > once. (this is quite easy since there are canned routines for this)
  25.  
  26. > Step 2: But then i just change only of its elements and compute its
  27. > determinant.
  28. > (Let G' be the new matrix)
  29.  
  30. > Step 2 is repeated quite a few times and each time G' differs from G at
  31. > just a single
  32. > element. So does any of you know about any public domain routine which could
  33. > perform step 2 more efficiently than just by computing the determinant? (like
  34. > finding the determinant of G' in terms of determinant of G and the
  35. > changed element).
  36.  
  37. > I looked into different techniques of evaluating the determinant. One
  38. > method was
  39. > to expand the determinant into a sum of n! terms and just grouping the
  40. > (n-1)! terms corresponding to the changed term. But my feeling was this would
  41. > be more time consuming than computing the determinant itself (which is of
  42. > order n**3 if LU factorisation is used). Correct me if i am wrong and 
  43. > is there any simpler technique to compute the determinant in such a case?
  44.  
  45. > Thanks
  46.  
  47. > Anand
  48.  
  49. I thought it would be a better idea to describe the motivation behind my
  50. interest
  51. in such a situation as described above. Probably I don't need to concern myself
  52. with the above problem.
  53.  
  54. The main motivation behind that was to solve a "non-linear eigenvalue"
  55. problem. 
  56. (I am not sure if i could it call it so, since i have never come across such a
  57. terminology before). I mean, the matrix itself is dependent on the eigenvalues.
  58. Something like G(lambda) = 0.0 where G is a square matix of order n.
  59. (For example: 
  60. IF it was a "linear" eigenvalue problem, then G(lambda) = lambda*I - A.)
  61. And i intend to solve the problem by a Newton Raphson routine. So i need to
  62. find the differential of the determinant of G(lambda) with respect to lambda.
  63.  
  64. f(lambda) = det(G(lambda))
  65.  
  66. df(lambda)/dlambda = d/dlambda (det(G(lambda)))
  67.  
  68. (And i came up with an expression for the same which goes something like this).
  69.  
  70. If G(lambda) = gij(lambda)    i = 1..n,  j = 1...n  (gij is the i-j th
  71. element of G)
  72.  
  73. then
  74.  
  75. df(lambda)/dlambda = (sum I = 1..n)(sum J = 1..n) det(GIJ (lambda))
  76.                         - n(n-1)*det(G(lambda))
  77.  
  78. where 
  79.  
  80. GIJ(lambda) = dgij/dlambda        if I = i, J = j
  81.  
  82.            = gij                if I not equal to i and J not equal to j
  83.  
  84. (what this means is that GIJ is same as G except that the I-J th element of GIJ
  85. is replaced by the correponding derivative.).
  86.  
  87. Thus my basic motivation is to find the differential of a determinant in terms
  88. of the determinant of the differentials. If there exists any better way
  89. of dealing
  90. with this problem than the technique which I am using above, then i
  91. wouldn't need 
  92. to find n**2 determinants.
  93.  
  94. The other option that i have is to use some standard canned package like
  95. MINPACK
  96. in netlib to solve the nonlinear problem G(lambda) = 0.0 and let MINPACK
  97. find the
  98. differential by using some sort of difference procedure.
  99.  
  100. Anand
  101.