Master thesis : Machine learning for a fast sparse triangular solve

Abstract

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.