Change search
ReferencesLink to record
Permanent link

Direct link
GPU Predictor-Corrector Interior Point Method for Large-Scale Linear Programming
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Numerical Analysis, NA.
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
GPU-accelererad inrepunktsmetod för storskalig linjärprogrammering (Swedish)
Abstract [en]

This master’s thesis concerns the implementation of a GPUaccelerated version of Mehrotra’s predictor-corrector interior point algorithm for large-scale linear programming (LP). The implementations are tested on LP problems arising in the financial industry, where there is high demand for faster LP solvers. The algorithm was implemented in C++, MATLAB and CUDA, using double precision for numerical stability.

A performance comparison showed that the algorithm can be accelerated from 2x to 6x using an Nvidia GTX Titan Black GPU compared to using only an Intel Xeon E5-2630v2 CPU. The amount of memory on the GPU restricts the size of problems that can be solved, but all tested problems that are small enough to fit on the GPU could be accelerated.

Abstract [sv]

Detta masterexamensarbete behandlar implementeringen av en grafikkortsaccelererad inrepunktsmetod av predictor-corrector-typ för storskalig linjärprogrammering (LP). Implementeringarna testas på LP-problem som uppkommer i finansbranschen, där det finns ett stort behov av allt snabbare LP-lösare. Algoritmen implementeras i C++, MATLAB och CUDA, och dubbelprecision används för numerisk stabilitet.

En prestandajämförelse visade att algoritmen kan accelereras 2x till 6x genom att använda ett Nvidia GTX Titan Black jämfört med att bara använda en Intel Xeon E5-2630v2. Mängden minne på grafikkortet begränsar problemstorleken, men alla testade problem som får plats i grafikkortsminnet kunde accelereras.

Place, publisher, year, edition, pages
TRITA-MAT-E, 2015:37
National Category
Computational Mathematics
URN: urn:nbn:se:kth:diva-168672OAI: diva2:818343
Subject / course
Scientific Computing
Educational program
Master of Science - Applied and Computational Mathematics
Available from: 2015-06-08 Created: 2015-06-07 Last updated: 2015-06-08Bibliographically approved

Open Access in DiVA

fulltext(855 kB)352 downloads
File information
File name FULLTEXT01.pdfFile size 855 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Numerical Analysis, NA
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 352 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 347 hits
ReferencesLink to record
Permanent link

Direct link