Feedback

Faculté des Sciences appliquées
Faculté des Sciences appliquées
MASTER THESIS
VIEW 359 | DOWNLOAD 49

Master thesis : Machine learning for a fast sparse triangular solve

Download
Di Raimo, Gaël ULiège
Promotor(s) : Louveaux, Quentin ULiège
Date of defense : 27-Jan-2023 • Permalink : http://hdl.handle.net/2268.2/16759
Details
Title : Master thesis : Machine learning for a fast sparse triangular solve
Author : Di Raimo, Gaël ULiège
Date of defense  : 27-Jan-2023
Advisor(s) : Louveaux, Quentin ULiège
Committee's member(s) : Geurts, Pierre ULiège
Huynh-Thu, Vân Anh ULiège
Language : English
Discipline(s) : Engineering, computing & technology > Computer science
Institution(s) : Université de Liège, Liège, Belgique
Degree: Master en ingénieur civil en informatique, à finalité spécialisée en "intelligent systems"
Faculty: Master thesis of the Faculté des Sciences appliquées

Abstract

[en] When solving simplex problems, multiple systems of linear equations are solved. This systems
are decomposed in their LU forms, where L and U are sparse. This triangular systems can be
solved with different algorithms that uses the sparse structure to save time. The context in which
an algorithm is faster than another is not well known, 3 of these algorithms referred as General
algorithm, Two-Phase algorithm and One-Phase algorithm can have very different computation
times to solve the systems. One could think to use Machine Learning techniques to learn in which context an algorithm is faster than others. However, the time window between the two fastest algorithms can be narrow. Therefore, fast models should be used to predict the fastest algorithm. One parameter which is expected to have a lot of information is the number of non-zero elements in the solution, a model will be tested to see if knowing this value can lead to better average computation time. A simple model classifying these algorithms is created using only information on b, the right-hand side. This model will be used to compared its performances with new models which are created.
The model that is proposed uses 4 regressions to predict the algorithm, one is used to predict the
number of non-zero elements in the solution which is used as feature for the 3 other regressions.
The other regressions predict the time needed by each algorithm and the classifier finally predict
the one with the lowest predicted time. RFAdaProxy (b) is the classifier proposed. This model
is able to solve the test set proposed in 34.78s whereas the simple model with just b information
needs 44.85s and the fictional model which would always predict the best algorithm obtained a
computation time of 19.95s.


File(s)

Document(s)

File
Access master_thesis_Gael_Di_Raimo.pdf
Description:
Size: 3.44 MB
Format: Adobe PDF

Author

  • Di Raimo, Gaël ULiège Université de Liège > Master ingé. civ. info., à fin.

Promotor(s)

Committee's member(s)

  • Geurts, Pierre ULiège Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Algorith. des syst. en interaction avec le monde physique
    ORBi View his publications on ORBi
  • Huynh-Thu, Vân Anh ULiège Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Algorith. des syst. en interaction avec le monde physique
    ORBi View his publications on ORBi
  • Total number of views 359
  • Total number of downloads 49










All documents available on MatheO are protected by copyright and subject to the usual rules for fair use.
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.