Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
2015.
Series
TRITA-MAT-E, 2015:37
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-168672OAI: oai:DiVA.org:kth-168672DiVA: diva2:818343
External cooperation
TriOptima AB
Subject / course
Scientific Computing
Educational program
Master of Science - Applied and Computational Mathematics
Supervisors
Examiners
Available from: 2015-06-08 Created: 2015-06-07 Last updated: 2015-06-08Bibliographically approved

Open Access in DiVA

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

By organisation
Numerical Analysis, NA
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 479 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

urn-nbn

Altmetric score

urn-nbn
Total: 431 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf