Interiör punkt metoder (IPM) med direkt lösning av de underliggande linjära system av ekvationer har använts framgångsrikt för att lösa mycket storskalig linjär programmering (LP) problem. Begränsningarna av direkta metoder för vissa klasser av problem har emellertid lett till att iterativa tekniker har övervägts. Den matrisfria metoden är en sådan metod och är så namngiven eftersom den iterativa lösningen procedur kräver endast resultaten av operationer Ax och A T y, där A är matrisen av begränsningskoefficienter. Det kan alltså i princip tillämpas på problem där A inte är känt och endast ett orakel finns tillgängligt för beräkning av Ax och A T y. Eftersom beräkningskostnaden för dessa operationer mycket väl kan dominera den totala lösningstiden för problemet, är det viktigt att de tekniker som används för att utföra dem är effektiva. Detta papper beskriver den matrisfria inre punkt metoden och, för flera klasser av LP problem, visar sin överväldigande överlägsen prestanda i förhållande till simplex metoden och IPM med ekvationer som lösts direkt. Den dominerande kostnaden för verksamheten Ax och A T y motiverar deras genomförande på en GPU för att ge ytterligare resultatvinster. Olika beräkningssystem för dessa glesa matris-vektorprodukter diskuteras. En jämförelse av den snabba upp som uppnåtts med hjälp av en mångkärnig GPU-implementation med att för en multi-core CPU-implementering indikerar att den förra har bättre potential.
REF accelererar den matrisfria inre punktmetoden för linjära program och uppnådde 4× speed-up för en 2,4 GHz AMD Opteron 2378 kärna jämfört med en NVIDIA Tesla C2070.
GPU Acceleration of the Matrix-Free Interior Point Method
{'venue': 'PPAM', 'journal': None, 'mag_field_of_study': ['Computer Science']}