Den hierarkiska interpolativa faktoriseringen (HIF) erbjuder ett effektivt sätt att lösa eller förkonditionera elliptiska partiella differentialekvationer. Genom att utnyttja operatörernas lokalitet och lågvärdiga egenskaper uppnår HIF kvasilinjär komplexitet för att faktorisera den diskreta elliptiska operatören och linjär komplexitet för att lösa det tillhörande linjära systemet. I detta dokument införs den distribuerade HIF (DHIF) som ett parallellt och distribuerat genomförande av HIF. DHIF organiserar processerna i en hierarkisk struktur och håller kommunikationen så lokal som möjligt. Beräkningen komplexitet är O N log N P och O N P för att konstruera och tillämpa DHIF, respektive, där N är storleken på problemet och P är antalet processer. Kommunikationskomplexiteten är latensen och β är den omvända bandbredden. Omfattande numeriska exempel utförs på TACC Stampede-systemet med upp till 4096 processer. De numeriska resultaten överensstämmer med komplexitetsanalysen och visar DHIF:s effektivitet och skalbarhet. En stor insats på området för vetenskaplig databehandling har ägnats åt en effektiv lösning av (2). Utöver O(N 3 ) komplexitet naiv matris inversion metod, kan man klassificera befintliga snabba algoritmer i följande grupper. Den första består av de glesa direkta algoritmerna, som utnyttjar det diskreta problemets gleshet. Det mest märkbara exemplet i denna grupp är den häckade dissektion multifrontal metod (MF) metod [14, 13, 24]. Genom att noggrant undersöka problemets gleshet och lokalisering, faktoriserar multifrontalmetoden matrisen A (och därmed A -1 ) som en produkt av glesa lägre och övre triangulära matriser. För 3D-problem kostar faktoriseringssteget O(N 2 ) verksamhet medan applikationssteget tar O(N 4/3 ) verksamhet. Många parallella genomföranden [3, 4, 27] av multifrontalmetoden föreslogs och de fungerar normalt ganska bra för problem av måttlig storlek. Men eftersom problemets storlek är större än ett par miljoner, har de flesta genomföranden, inklusive de distribuerade, drabbats av allvarliga flaskhalsar i minneskonsumtionen. Den andra gruppen består av iterativa lösare [9, 29, 30], inklusive berömda algoritmer såsom konjugat gradient (CG) metod och multigrid metod. Varje iteration av dessa algoritmer tar normalt steg O(N ) och därmed den totala kostnaden för att lösa (2) är proportionell mot antalet iterationer som krävs för konvergens. För problem med smidiga koefficientfunktioner a(x) och b(x) är antalet iterationer vanligtvis ganska litet och den optimala linjära komplexiteten uppnås. Men om koefficienten funktioner saknar regelbundenhet eller har hög kontrast, iteration antalet vanligtvis växer ganska snabbt som problemet storlek ökar. Den tredje gruppen innehåller metoder baserade på strukturerade matriser [7, 6, 8, 11]. Dessa metoder, till exempel H-matrisen [16, 18], H 2 -matrisen [17], och den hierarkiskt semi-skiljbara matrisen (HSS) [10, 38], visas ha effektiva approximationer av linjär eller kvasi-linjär komplexitet för matriserna A och A −1. Som ett resultat, algebraiska operationer av dessa matriser är av linjär eller kvasi-linjär komplexitet också. Mer specifikt är rekursiv inversion och inversion av raketstil [1] två populära metoder för invers drift. För distribuerade minnesimplementeringar saknar dock den förra en parallell skalbarhet [22, 23] medan den senare endast visar skalbarhet för 1D- och 2D-problem [1]. För 3D-problem lider dessa metoder vanligtvis av stora faktorer som gör dem mindre effektiva för praktiska storskaliga problem. En nyligen genomförd grupp av metoder utforskar idén att integrera MF-metoden med den hierarkiska matrisen [25, 37, 35, 36, 15, 34, 19] eller block low-rank-matrisen [31, 32, 2] för att utnyttja båda metodernas effektivitet. I stället för att direkt tillämpa den hierarkiska matrisstrukturen på 3D-problemen tillämpar dessa metoder den på representationen av frontmatriserna (dvs. interaktionerna mellan de nedre dimensionsfronterna). Dessa metoder är av linjär eller kvasilinjär komplexitet i teorin med mycket små förfaktorer. Men på grund av den kombinerade komplexiteten, genomförandet är mycket icke-trivial och ganska svårt för parallellisering. På senare tid föreslås den hierarkiska interpolativa faktoriseringen (HIF) [20, 21] som ett nytt sätt att lösa elliptiska PDE och integrala ekvationer. Jämfört med multifrontal metoden, innehåller HIF ett extra steg av skelettisering fronterna för att minska storleken på de täta frontalmatriser. Baserat på den viktiga observationen att antalet skelettpunkter på varje front skalor linjärt som endimensionella fronter, HIF faktoriserar matrisen A (och därmed A -1 ) som en produkt av glesa matriser som innehåller endast O (N ) icke-noll poster totalt. Dessutom, faktorisering och tillämpning av HIF är komplexa O(N log N ) och O(N ), respektive, för N är det totala antalet grader av frihet (DOF) i (2). I praktiken visar HIF betydande besparingar när det gäller de beräkningsresurser som krävs för 3D-problem.
Resultaten av hierarkisk interpolativ nedbrytning i en distribuerad minnesmiljö rapporteras i REF.
Distributed-memory Hierarchical Interpolative Factorization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}