Master thesis : Machine learning for a fast sparse triangular solve
Di Raimo, Gaël
Promotor(s) : Louveaux, Quentin
Date of defense : 27-Jan-2023 • Permalink :
|Master thesis : Machine learning for a fast sparse triangular solve
|Di Raimo, Gaël
|Date of defense :
|Committee's member(s) :
Huynh-Thu, Vân Anh
|Engineering, computing & technology > Computer science
|Université de Liège, Liège, Belgique
|Master en ingénieur civil en informatique, à finalité spécialisée en "intelligent systems"
|Master thesis of the Faculté des Sciences appliquées
[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.
Cite this master thesis
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.