文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > A=A1M2+M1A22Rn1n2n1n2
侵权投诉

A=A1M2+M1A22Rn1n2n1n2

mistosolvethelinearsystemAu=f,wheretheseparablematrix

A PARALLEL FAST DIRECT SOLVER WITH APPLICATIONS Raino A. E. Makinen Tuomo Rossi Jari Toivanen Laboratory of Scienti c Computing, Department of Mathematics University of Jyvaskyla, Jyvaskyla, Finland

1. PARALLEL FAST DIRECT SOLVER

1.1 SEPARABLE MATRICES em is to solve the linear system Au= f, where the separable matrix A= A 1 M2+ M 1 A 2+ M 1 M 2 2 C n n i n1 n2 n1 n2

;

M 2 C i i, i= 1; 2, and A2 are symmetric and tridiagonal, and M2 are diagonal, and

The parallel solution of partial solution problems:{ small ones using one processor per problem{ large ones using several processors per problem MPI implementation using:{ point{to{point communication{ communicators to work with subsets of processors{ collective broadcast and reduce operations Using FORTRAN subroutine called PDC2D Rossi, Toivanen, 1996] Block dimensions are n1= n2= n Comparison to BLKTRI Swarztrauber, Sweet, 1979]:{ single processor e ciency{ accuracy 100 parallel efficiency in% 90 80 70 60 50 40 200 400 600 p=1 p=2 p=4 p=8 p=16 p=32 p=64 800 1000 1200 1400 1600 1800 2000 n

2.3 TIME{HARMONIC ELECTROMAGNETIC SCATTERING

3. CONCLUSIONS

1.5 NUMERICAL EXPERIMENTS

R k k s s

means the matrix tensor (Kronecker) product: B 2 C and C 2 C=) B C= fB C g=1 2 C . k ks ks i;j i;j

2, the mesh spacing in x{direction is denoted by h . that the coe cient matrix A has the structure i i

= (jruj2 )= 1+

? 1 M 2 (1? jruj2 ) 2 1

?1

1

:

parallel efficiency in%

chlet b.v.p. for the Poisson equation in a rectangle, retization using piecewise linear nite elements, and orm rectangular, triangulated mesh with n1 n2 inner nodes.

The Maxwell equations can be reduced to the Helmholtz equation in the case PSCR{method is applicable to large class of problems: of two{dimensional time{harmonic electromagnetic scattering.{ Dirichlet, Neumann or Newton boundary conditions, The scattered wave is given by the complex valued function v which solves the Helmholtz equation:{ complex valued problems, 2 v= 0 in; v+!{ discretizations possible with nonuniform meshes, v=?g on S;{ arbitrary matrix block dimensions. rv n= Rv on?1; Figure 3. A mesh partitioning for four processors. where the wave number is != 2= and is the wave length. S denotes PDC2D{implementation is MPI based and, thus, portable. It has a the surface of a scatterer and?1 denotes an arti cial far eld boundary on good scalability, single processor e ciency and accuracy. which the second{order absorbing boundary condition rv n= Rv is posed. 2.2 SUBSONIC FULL POTENTIAL FLOWS It is easy to make a parallel implementation of the ctitious domain The nite element the previous problems leads a linear Full potential ow models perfect compressible inviscid and irrotational uid system of equationsapproximation of symmetric coe cient matrix.toThis sysmethod with PDC2D. with a complex ows. tem is solved by the GMRES{method with a ctitious domain preconditioner Large problems can be solved e ciently in parallel with the con

sidered A ow around an airfoil with the surface S is computed in an exterior domain Toivanen, 1996], Kuznetsov, Lipnikov, 1992]. ctitious domain preconditioners. which is truncated by an arti cial far eld boundary?1 . In this problem, it is possible to perform the iterations in a small subspace The quality of the preconditioner is independent of the number of proThe potential u is the solution of the following Neumann boundary value Kuznetsov, 1985]. Hence, tha GMRES{method can be used without restarts. cessors unlike with most of the domain decomposition methods. problem 100?r ( ru)= 0 in; ru n= 0 on S; 80 ru n= g on?1; Acknowledgements. The authors are grateful to Prof. Yuri A. Kuznetsov for valuable discussions about the PSCR method and its considered applications. where n denotes the outward unit normal vector for the domain, and g is 60 The research was supported by the Academy of Finland, Grant 34063. the normal component of the velocity. The density is given by 40 p=1 p=2 p=4 p=8 p=16 100000 N 1000000

ial solution technique is based on the separation of variables, which s advantage of the sparsity in Fourier transformations number of steps is O(log n1 ) and each step requires O(n1 n2 ) ops the total computational cost is O(n1 n2 log n1 ) y similarities to the partial fraction variant of Cyclic Reduction eet, 1988]

parallel efficiency in%

n 63 127 255 511 1023 2047 PDC2D init. 0.059 0.225 0.855 3.419 13.808 56.691 A(u)u= f; BLKTRI init. 0.004 0.015 0.055 0.207 0.858 3.286 which is solved by the Newton method: PDC2D solve 0.005 0.028 0.116 0.591 3.403 27.431 BLKTRI solve 0.013 0.071 0.335 1.699 8.248 48.659 0= 0;+1= u? (D )+ (A(u )u? f ); u u k= 1; 2;:::; Table 1. CPU{time usage (in seconds) with one Cray T3E{750 processor. where (D )+ is the pseudo{inverse of the Jacobian matrix D evaluated at 1.2 PSCR{METHOD the point u . n 63 127 255 511 1023 2047 oduced in Vassilevski, 1984]; generalizations in Kuznetsov, 1985] The linear systems involving the Jacobian matrices D can be solved e PDC2D 0.00160 0.00769 0.06691 0.03955 0.19493 1.01509 Kuznetsov, Rossi, 1996] ciently with the parallel ctitious domain method Rossi, Toivanen, 1997]. BLKTRI 0.00911 0.03683 0.05872 0.92631 4.79920 5.77315 embles the classical Cyclic Reduction, the solution is obtained by Table 2. Comparison of errors in maximum norm scaled by 1011. orming the reduction steps and the back{substitution steps 100 ach step, the arising problems are solved using the partial solution Using 64 processors in the Cray T3E{750, the solution of 1023 1023 problem 95 requires 0.08 seconds and the speedup is 45. nique Banegas, 1978], Kuznetsov, Matsokin, 1978] i i n n i

A= A1 M2+ M1 A2 2 R matrices A and M are de ned by A= 1i tridiag f?1; 2;?1g 2 R i M= h I 2 R i i; i= 1; 2: h n n i i

n1 n2

n1 n2

;

Figure 1. Parallel e ciency of PDC2D in Cray T3E{750.

i

and

The Mach number of the free stream is M1 and is the ratio of speci c heats (= 1:4 for air). This l

eads to the solution of nonlinear system of the form

20

REFERENCES Banegas, 1978] A. Banegas: Fast Poisson solvers for problems with sparsity, Math. Comp., 37(1978), pp. 441{446. Kuznetsov, 1985] Yu.A. Kuznetsov: Numerical methods in subspaces, in Vychislitel'nye Processy i Sistemy II, G.I. Marchuk, ed., Nauka, Moscow, 1985, pp. 265{350. In Russian. Kuznetsov, Lipnikov, 1992] Yu.A. Kuznetsov and K. N. Lipnikov: Fictitious domain method for solving the Helmholtz wave equation for unbounded domain, in Numerical Methods and Mathematical Modelling, Institute of Numerical Mathematics of Russian Academy of Sciences, Moscow, 1992, pp. 56{69, In Russian. Kuznetsov, Matsokin, 1978] Yu.A. Kuznetsov and A.M. Matsokin: On partial solution of systems of linear algebraic equations, Vychislitel'nye Metody Lineinoi Algebry, G.I. Marchuk, ed., Vychisl. Tsentr Sib. Otdel. Akad. Nauk SSSR, Novosibirsk, 1978, pp. 62{89. In Russian, English translation in: Sov. J. Numer. Anal. Math. Modelling, 4(1989), pp. 453{468. Kuznetsov, Rossi, 1996] Yu.A. Kuznetsov and T. Rossi: Fast direct method for solving algebraic systems with separable symmetric band matrices, East{West J. Numer. Math., 4(1996), pp. 53{68. Marchuk, Kuznetsov, Matsokin, 1986] G.I. Marchuk, Yu.A. Kuznetsov, A.M. Matsokin: Fictitious domain and domain decomposition methods, Sov. J. Numer. Anal. Math. Modelling 1(1986), pp. 3{35. Rossi, Toivanen, 1996] T. Rossi and J. Toivanen: A parallel fast direct solver for block tridiagonal systems with separable matrices of arbitrary dimension, SIAM J. Sci. Comput., to appear. Rossi, Toivanen, 1997] T. Rossi and J. Toivanen: Parallel ctitious domain method for a nonlinear elliptic neumann boundary value problem, Tech. Rep. 16, Laboratory of Scienti c Computing, Department of Mathematics, University of Jyvaskyla, Jyvaskyla, Finland, 1997. Swarztrauber, Sweet, 1979] P.N. Swarztrauber and R.A. Sweet: Algorithm 541: E cient fortran subprograms for the solution of separable elliptic partial di erential equations, ACM Trans. Math. Software, 5(1979), pp. 352{364. Sweet, 1988] R.A. Sweet: A parallel and vector variant of the cyclic reduction algorithm, SIAM J. Sci. Stat. Comput., 9(1988), pp. 761{765. Toivanen, 1996] J. Toivanen: Numerical experiments with coupled ctitious domain and domain decomposition method for 2D Helmholtz equation, Tech. Rep. 14, Laboratory of Scienti c Computing, Department of Mathematics, University of Jyvaskyla, Jyvaskyla, Finland, 1996. Vassilevski, 1984] P.S. Vassilevski: Fast algorithm for solving a linear algebraic problem with separable variables, C. r. Acad. Bulg. Sci., 37(1984), pp. 305{308.

0

Figure 6. Parallel e ciency of the Helmholtz solver in Cray T3E{750. iter solve 31 1.15 37 1.98 42 4.27 49 15.16 58 61.70 69 269.55 Table 4. The test runs with the Helmholtz solver in Cray T3E{750. 161 241 401 721 1361 2641 97 113 145 209 337 593

k

k

k

k

k

n1 n2

k

k

k

k

90 85 80 75 np=1 np=2 np=4 p p

2. APPLICATIONS 2.1 FICTITIOUS DOMAIN

METHOD

1.3 RADIX FOUR PSCR{METHOD

dix four variant of the PSCR{method reduces the number of equas by the factor four in each reduction step his sense, the classical Cyclic Reduction is a radix two method computational cost of the PSCR{method is

flops(n1; n2 )= (44 log4 (n1+ 1)? 163 )n1 n2 4

radix two variant requires 50% more ops than the radix four ant parallel implementation is a radix four variant, since it is almost mal with respect to the computational cost

70 n=8 The original problem posed on a domain with complicated shape is ren=16 Figure 7. The scattering by a 300 wavelength{long obstacle. 65 placed by an equivalent problem on a larger domain with simple shape, 10000 100000 like rectangle or circle The asymptotic behavior of the scattered wave can be illustrated by the radar N The enlarged problem is discretized with the nite element method us- Figure 4. Parallel e ciency of the full potential solver in Cray T3E{750. cross section (RCS) plot. ing meshes which are rectangular and locally tted to the boundary of the original domain 270 n1 n2 nodes init solve outer inner 300 240 46 51 2319 0.10 0.83 3 105 The enlarged problem is solved with a suitable preconditioned itera91 101 9046 0.20 3.84 3 106 tive method with a preconditioner which is constructed for the en210 181 201 35737 0.52 16.20 3 111 330 larged problem on simple shaped domain using fully rectangular mesh 361 401 142073 1.65 75.50 3 116 Marchuk, Kuznetsov, Matsokin, 1986] 721 801 566520 5.88 343.35 3 124 In our applications, the linear systems involving the preconditioner can 0 180 be solved in parallel by the PDC2D{implementation. To obtain a Table 3. The test runs with the full potential ow solver in Cray T3E{750. -30 -20 method with good scalability, the matrix{vector multiplication needs -10 also to be parallelized 0

30

10 20

150 30 dB

0.62

60 0.54 0.46 0.38

120 90

1.4 PARALLEL IMPLEMENTATION mber of processors n= 2 p k

Figure 8. The RCS for the 300 wavelength{long obstacle. 6081

a partitioning: each process has approximately the same amount of or blocks of size n2

Figure 2. A part of locally tted mesh for NACA64A410.

Figure 5. The Mach number eld for a ow around NACA64A410.

The problem with the 300 wavelength{long obstacle is discretized with 1799 mesh which has 20 nodes per wavelength. The solution required 109 iterations and less than 10 minutes in wall clock time with 16 Cray T3E{750 processors.

A=A1M2+M1A22Rn1n2n1n2

第1页

TOP相关主题

你可能喜欢

热门文档

相关文档

  • 二次函数y=a(x-h)2+k的图像和性质

    二次函数y=a(x-h)2+k的图像和性质_数学_初中教育_教育专区。二次函数(a≠0) 的图象与性质 (1)复习: ①在同一直角坐标系内,画出函数 y ? x 2 y ...

  • 二次函数y=a(x-h)2的图象与性质

    2、按下列要求求出二次函数的解析式: 按下列要求求出二次函数的解析式: 已知抛物线y=a(x y=a(x- 经过点( (1)已知抛物线y=a(x-h)2经过点(-3,2) ...

  • =a

    =a_专业资料。\Gamma (e z v \Gamma e y w)=ae e x (fl \Gamma 1)u=a 2 e y \GammaIn summary, the development of some computational ...

  • a2+2ab+b2=(a+b)2 a2-2ab+b2=(a-b)2的变化应用

    a2+2ab+b2=(a+b)2 a2-2ab+b2=(a-b)2的变化应用_初一数学_数学_初中教育_教育专区。这是专题延伸,注意选择使用。a2+2ab+b2=(a+b)2 a2-2ab+b...

  • 二次函数y=a(x-h)2+k的图像及其性质练习

    二次函数y=a(x-h)2+k的图像及其性质练习_初三数学_数学_初中教育_教育专区。二次函数y=a(x-h)2+k的图像及其性质练习二次函数 y=a(x-h)2+k 一 ...

  • unit2 section A (1a=2d)

    A.a picture B.picture C.pictures D.nice pictures ( C)4.Are ___ Kate’s ___? A.this, book B.that,book C.these,books D.those,book ( D )5...

  • 2.2 二次函数y=a(x-h)^2+k的图象与性质(4)

    2.2 二次函数y=a(x-h)^2+k的图象与性质(4)_数学_初中教育_教育专区。今日推荐 88份文档 2014全国高考状元联手分享状元笔记...

  • 27.2.4_二次函数y=a(x-h)2+k的图像与性质

    27.2.4_二次函数y=a(x-h)2+k的图像与性质_数学_初中教育_教育专区。2 二次函数y=a(x-h) +k的图 象及其性质 1请说出二次函数y=ax? +k与y=ax...

  • 二次函数y=ax2+bx+c的图像与系数符号a,b,c的关系

    二次函数 y=ax2+bx+c 的图像与系数符号 a,b,c 的关系 姓名___ 一、知识要点 二次函数 y=ax2+bx+c 系数符号的确定: (1)a 由抛物线开口方向确定:开口...

  • 已知= - (a>0),求 的值

    a ?3 x (a x ? a ? x )[(a x ? a ? x ) 2 ? a x a ? x ] x ?x x ?x x = =( a + a )2- a a 。又因 a = 6 - 5 , x...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email