Abstrakt. Detta dokument presenterar en ny partitionerad algoritm för LU nedbrytning med partiell pivoting. Den nya algoritmen, som kallas den rekursivt separerade algoritmen, är baserad på en rekursiv partitionering av matrisen. I tidningen analyseras lokaliseringen av referensen i den nya algoritmen och lokaliseringen av referensen i en känd och allmänt använd partitionerad algoritm för LU nedbrytning som kallas den rätt utseende algoritmen. Analysen visar att den nya algoritmen utför en faktor av (p M=n) färre I/O operationer (eller cache missar) än den högra algoritmen, där n är ordningen på matrisen och M är storleken på primärminnet. Analysen bestämmer också den optimala blockstorleken för den rätt utseende algoritmen. Experimentella jämförelser mellan den nya algoritmen och den rätta algoritmen visar att en implementering av den nya algoritmen överträffar en på liknande sätt kodad algoritm med rätt utseende på 6 olika RISC-arkitekturer, att den nya algoritmen utför färre cachemissar än någon annan algoritm som testats, och att den bene ts mer från Strassens matrismultiplikationsalgoritm.
) I/O-operationer ges för LU-nedbrytning utan pivoting; algoritmen i REF utför LU-nedbrytning med partiell pivoting inom samma I/O-gräns.
Locality Of Reference In Lu Decomposition With Partial Pivoting
{'venue': 'SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS', 'journal': None, 'mag_field_of_study': ['Mathematics']}