From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) Subject: Re: special linear system... Date: 31 Jul 2000 14:48:27 -0400 Newsgroups: sci.math.num-analysis Summary: [missing] In article <8m42gm$b9es3$1@hades.rz.uni-sb.de>, wrote: :hi, : :i try to solve a linear system of the form : : [ A B ] : [ C D ] : :A, B,C and D are upper-triangular. : :is there any effient way to solve such a system or :do i have to use the standart LU-decomposition ? : I can offer four LU (or UL) block decompositions, two of each assuming and using the invertibility of A or of D, respectively. (There might be more such decompositions, assuming the invertibility of C or D, after you permute the blocks.) A\B means inv(A)*B , and can be performed without inverting A. C/A means C*inv(A) with a similar remark. [ A 0 ] [ C D-C*(A\B) ] times [ I A\B ] [ 0 I ] Next: [ I 0 ] [ C/A I ] times [ A B ] [ 0 D-(C/A)*B ] Next: [ I B/D ] [ 0 I ] times [ A-(B/D)*C 0 ] [ C D ] Next: [ A-B*(D\C) B ] [ 0 D ] times [ I 0 ] [ D\C I ] The "Schur complements" A-B*inv(D)*C etc. come out upper triangular in your situation. Some factors are not exactly upper triangular but still of enough special structure (triangular after a block permutation) to be taken advantage of. If all A, B, C, D are singular, standard pivoted P'LU decomposition is in order. Cheers, ZVK(Slavek). ============================================================================== From: "Serge Kanilo" Subject: Re: special linear system... Date: Tue, 01 Aug 2000 19:38:26 GMT Newsgroups: sci.math.num-analysis wrote in message news:8m42gm$b9es3$1@hades.rz.uni-sb.de... > hi, > > i try to solve a linear system of the form > > [ A B ] > [ C D ] > > A, B,C and D are upper-triangular. > > is there any effient way to solve such a system or > do i have to use the standart LU-decomposition ? > > yours, uwe. > -- > Uwe Schmitt | Institut für Angewandte Mathematik > Uwe.Schmitt@num.uni-sb.de | Universität des Saarlandes > phone: +49 (0)681/302-2468 | Geb. 36.1, Zi. 4.17 > fax: +49 (0)681/302-4435 | PF 151150 > private: +49 (0)681/397052 | D-66041 Saarbrücken You can do a very effective LU decomposition. 1. Let's rearrange rows and columns. First row of the first block, first row of the second block, second row of the fist block, second row of the second block, .... The same with the columns. A11 B11 A12 B12 ... C11 D11 C12 C12 ... 0 0 A22 B22 ... 0 0 C22 D22 ... ... ... And we get *almost* upper triangular matrix. Or block upper tridiagonal with block size 2x2. 2. Then solve the last 2x2 system, do substitution, go to upper diagonal block, ... and up to 1st. All you need is solve N 2x2 systems. And 2*N*(N-1) addition/multiplication. That's all. Hope this helps. Serge Kanilo PS: Looks like solution for complex unknown. Just a thought.