Abstrakt. Motiverade av tillämpningar där data kan formuleras som en matris, anser vi algoritmer för flera vanliga linjära algebra problem. Dessa algoritmer gör effektivare användning av beräkningsresurser, såsom beräkningstid, slumpmässigt åtkomstminne (RAM), och antalet passerar över data, än vad som tidigare känt algoritmer för dessa problem. I den här artikeln, vi utformar två algoritmer för matris multiplikation problem. Antag att A och B (som är m × n respektive n × p) är de två ingående matriserna. I vår huvudalgoritm utför vi c oberoende prövningar, där i varje försök vi slumpmässigt prov ett element av {1, 2,...., n} med en lämplig sannolikhetsfördelning P på {1, 2,..., n}. Vi bildar en m × c matris C som består av de prover kolonner av A, varje skalas lämpligt, och vi bildar en c × n matris R med hjälp av motsvarande rader av B, återigen skalas lämpligt. Valet av P och kolumnen och radskalning är avgörande funktioner i algoritmen. När dessa väljs klokt visar vi att CR är en bra approximation till AB. Mer exakt visar vi att var · F betecknar Frobenius norm, dvs, A 2 A 2 ij. Denna algoritm kan implementeras utan att matriserna A och B lagras i RAM, förutsatt att den kan göra två passager över de matriser som lagras i externt minne och använda O(c(m + n + p)) ytterligare RAM för att konstruera C och R. Vi presenterar sedan en andra matris multiplikationsalgoritm som liknar vår huvudalgoritm. Dessutom presenterar vi en modell (pass-effektiv modell) där effektiviteten av dessa och andra ungefärliga matrisalgoritmer kan studeras och som vi hävdar är väl lämpad för många tillämpningar som omfattar massiva datamängder. I denna modell är de knappa beräkningsresurserna antalet passager över data och det extra utrymme och den tid som krävs av algoritmen. Indatamatriserna kan presenteras i valfri ordning i posterna (och inte bara rad- eller kolumnordning), vilket är fallet i många tillämpningar där t.ex. data har skrivits in av flera agenter. Dessutom får inmatningsmatriserna presenteras i en glesrepresentation, där endast icke-nollposter skrivs.
REF visade hur en enklare provtagningsstrategi kan leda till en god approximation av blanketten CR, där matriserna C och R består av c-kolumner respektive c-raderna A respektive B.
Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication
{'venue': 'SIAM Journal on Computing', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}