page 1  (11 pages)
2to next section

methodsiterativeandorderingsMulticolour

equationsellipticfor

ChristaraC.Christina

SciencesComputerofDepartment

TorontoofUniversity

1A4M5SCANADA,Toronto,

ccce-mail: @cs.toronto.edu

Abstract

andperformancethestudywepaperthisIn
methodsiterativeofimplementationparallel
discreti-thefromarisingsystemslineartoapplied
ProblemsValueBoundaryellipticlinearofsation
multicolourtoaccordingorderedarewhich(BVP)
BVPaofdiscretisationtheviewWeorderings.
equationsofsetageneratingofprocessaas
orderedwhenequations,Thesestencils.between
inresultstencil,theofindexingsometoaccording
ofeffectthediscussWesystem.linearsparsea
ofpatternsparsitytheonstencilstheofindexing
iterativeofconvergencetheonsystem,linearthe
theonaswellassystem,thetoappliedmethods
Wemethods.theseofimplementationparallel
inpreferableareindexingsstencilwhichdiscuss
message-incommunicationminimisetoorder
architectures.parallelpassing

Overview0.

generaldiscussbrieflywe1,SectionIn
ellipticlinearofcomputationparalleltheonissues
2,SectionIn(BVPs).ProblemsValueBoundary
discretisationBVPcommonsomerecallwe
weequations,stencilastheseviewwemethods,
somewhenarisingsystemlinearoftypetheshow
SectionInadopted.areindexingsstencilcommon
conver-theonresultsexperimentalpresentwe3,
requirementsmemoryandcomplexitytimegence,
systems.linearsuchonmethodsiterativesomeof
paralleltheonissuesdiscusswe4,SectionIn
toappliedmethodsiterativeofimplementation
com-theonfocusWeabove.assystemslinear
sten-chosenthehowandrequirementsmunication
5,SectionFinally,these.affectcanindexingcil
resultsperformancepreliminarysomeincludes
iterativesomeofimplementationthefrom
hypercube.iPSC/2theonmethods

__________________ ? 1991Christara,C.ChristinabyCopyright

com-parallelandproblemsvalueBoundary1.
putation.

ellipticlinearofcomputationparallelThe
thanmorein(BVPs)ProblemsValueBoundary
ofinteresttheattractedhasdimensionsone
fewpasttheoverresearchersofnumberincreasing
includ-reasons,severaltodueisfactThisyears.
scientistsappliedofdemandincreasingtheing
accuratelyproblemssuchsolvetoengineersand
tocostcomputationalhightheefficiently,and
aswellassolutions,efficientandaccurateobtain
BVPs.inparallelismofhigh-degreeinherentthe

anbydescribedareBVPsEllipticLinear
defined(PDE)EquationDifferentialPartialelliptic
domainsomein W

LI u(x) = g in(x) W (1.1)

theondefinedconditionsboundarysomeand
boundary ?W of W

BI u(x) g= on(x) ?W (1.2)

differentialpartialellipticlinearaisLIwhere
operator,differentialboundaryaisBIoperator, g and g (multi-dimensional)xoffunctionsgivenare and u x.offunctionunknowntheis

becanBVPsofsolutionnumericalThe
thefirstAtprocessing.three-phaseaasviewed
overdiscretisedis(1.1)-(1.2)problemcontinuous
ofelementsorpointsdiscretisationofseta
W __
W? ??W methoddiscretisationsomeusing, isThisetc).element,finitedifference,(finite
thecalled discretisation setaisresultThephase. ofnumberTheequations.linear(discrete)of
discretisationthefinehowondependsequations
isequationperunknownsofnumberthebutis,
ofnumbertheofindependentandsmalloften
calledphase,secondtheInequations. indexing, isunknownsandequationstheoforderingan
theequationsofsetthetogivingthusadopted,
pat-sparsityparticularawithsystem,aofform
equationstheoforderingthecasesmostIntern.
pointstheoforderingthefollowsunknownsand
phase,thirdThediscretisation.theofelementsor
astoreferred solution theofsolutiontheinvolves,