From: Prasanth Nair Subject: Re: Solution when there is a delta change in matrix! Date: Mon, 27 Sep 1999 21:19:44 +0100 Newsgroups: comp.parallel.pvm,sci.math.num-analysis Keywords: Sherman-Morrison-Woodbury Formula Sunil Hadap wrote: > Hi! > > Suppose I have a solution to Ax=b using any of the standard methods, > matrix A is fully dense. Now in my problem matrix A undergoes a minor > change, some or all of the elements change a little. Are there any > methods developed, or can be thought of to successively compute a new > solution b for the new matrix A, from old system and solution. It can > be with some error, so I can go on getting the solution for some time > before the error is too much, then I recompute the accurate solution > using standard methods. > > If this is possible, great! > > Regards > > Sunil If an approximate solution will do, there is a variety of methods you can choose from. I'll outline some of them below. Let Delta(A) be the perturbation matrix, and x be the solution of the old/original system, i.e, Ax = b. The problem is to approximate x', i.e., the solution of (A + Delta(A)) x' = b. ------> (1) x' can be written as a binomial series (also referred to as the Neumann expansion scheme) of the form x' = ( I - B + B^2 - B^3 + .......) x ---> (2) where B = inv(A)*Delta(A). Notes - (1) The terms B*x, B^2*x, etc. can be computed without explicitly computing inv(A); i.e., using the factored form of A in a recursive fashion. (2) The Binomial series will not converge if ||B|| > 1, i.e., for large perturbations. For improving the accuracy SIGNIFICANTLY, use the terms of the binomial series as basis vectors for representing x', i.e., x' = c1*r1 + c2*r2 + .... c2*rm ------> (3) where c1, c2, ... cm are undetermined scalars; r1 = x, r2 = -B*x, ....., rm = (-1)^(m-1)*B^(m-1)*x are the m basis vectors. The undermined scalars can be found using equations (1) and (3), i.e., write eqn. (3) using matrix notation as x' = [ R] {c}, substitute in eqn (1), and premultiply both sides by [R]^{T}. This gives a system of m x m equations to be solved for {c} Notes - (1) m = 2,3 is generally sufficient to ensure good accuracy in the approximation procedure; see the results reported in Ref [1], which introduces this method. (2) When rank(Delta(A)) << n, a simple reformulation can enable the computation of "exact" results in a computationally efficient fashion; see Ref [2] for more details. [1] Kirsch, U., "Reduced Basis Approximation of Structural Displacements for Optimal Design," AIAA Journal, Vol. 29, No. 10, 1991, pp. 1751-1758. [2] Akgun, M.A, Garcelon, J. H., and Haftka, R.T., Exact Static Structural Reanalysis in Relation to the Sherman-Morrison-Woodbury Formulas, ISSMO/NASA/AIAA First Internet Conference on Approximation and Fast Reanalysis Techniques in Engineering Optimization, June 14-27, 1998. http://www.aero.ufl.edu/~akgun Hope this helps. -Prasanth ----------------------------------------- Prasanth B. Nair Computational Engineering and Design Center University of Southampton, Highfield Southampton SO17 1BJ, U.K. Phone : +44-1703-595068 Fax : +44-1703-593230 email : P.B.Nair@soton.ac.uk WWW : http://www.soton.ac.uk/~pbn ----------------------------------------- ============================================================================== From: sclark@its.leeds.ac.uk (Stephen D Clark) Subject: Re: Solution when there is a delta change in matrix! Date: Mon, 20 Sep 1999 12:30:24 +0100 (BST) Newsgroups: comp.parallel.pvm,sci.math.num-analysis See "Numerical Receipes in C" (or Pascal or FORTRAN) by Press, Teukolsky, Vetterling and Flannery, pages 73-74 for a discussion of the Sherman-Morrison Formula which does what you ask. If you can not find the book in your local library, it is available on the web. Email me for a URL. Sunil Hadap wrote: > Hi! > > Suppose I have a solution to Ax=b using any of the standard methods, > matrix A is fully dense. Now in my problem matrix A undergoes a minor > change, some or all of the elements change a little. Are there any > methods developed, or can be thought of to successively compute a new > solution b for the new matrix A, from old system and solution. It can > be with some error, so I can go on getting the solution for some time > before the error is too much, then I recompute the accurate solution > using standard methods. > > If this is possible, great! > > Regards > > Sunil ============================================================================== From: klimpelt Subject: Re: Sherman-Morrison-Woodbury formula Date: Mon, 25 Oct 1999 19:08:23 +0200 Newsgroups: sci.math.num-analysis Luan V Nguyen wrote: > This statement is the first part of the Sherman-Morrison-Woodbury Can anyone give me a histoty of the Sherman-Morrison-Woodbury formula. I once read something in a book about sparse matrices, that it was found in about 1950, later been generalised, and that 1973, a conection to sparse matrices was found The Formula gives the inverse of something like M=A+USV The conection found in 1973 goes something like this Ax+USVx=b is equivalent to Ax+Uy = b Vx-S^-1y = 0 when you write this as a matrix (H=-S^-1) equation, (A U) (x) = (b) (V H) (y) = (0) and use Gaussian elimination on the blocks, you obtain the formula. Does Sherman,Morrison and Woodbury have really found the formula, without being aware of this interpretation? (Or at least without publishing it?) Any information would be appreciated very much Thomas ============================================================================== From: jzhang@cs.engr.uky.edu (Jun Zhang) Subject: Re: Sherman-Morrison-Woodbury formula Date: 25 Oct 1999 18:21:29 GMT Newsgroups: sci.math.num-analysis How about the paper by William W. Hager "Updating the Inverse of A Matrix", SIAM Review, Vol. 31, No. 2, pp. 221-239, 1989. The paper contains some historic accounts, including the typographic errors of the original paper. Jun Zhang --------- In article <38148E87.956EE3DA@hivaoa.unice.fr>, klimpelt wrote: [previous article quoted --djr] ********************************************************************** * Jun Zhang * E-mail: jzhang@cs.uky.edu * * Department of Computer Science * URL:http://www.cs.uky.edu/~jzhang * * University of Kentucky * Tel:(606)257-3892 *