Harokopio University
A study of computational and algorithmic techniques for solving complex computational problems
Abstract
dc:descriptionIn this doctoral thesis, a new sparse approximate pseudoinverse matrix technique for solving sparse least squares problems is introduced. In order to solve these least squares problems, preconditioned iterative methods are used for both overdetermined and underdetermined systems. A new approximate pseudoinverse preconditioning scheme, the Generic Approximate Sparse Pseudoinverse (GASP) schema, based on modified incomplete QR factorizations with Givens rotations, is designed and implemented. These techniques are adapted for parallel environments by introducing the new parallel Generic Sparse Approximate Pseudoinverse (ParGASP) schema. This scheme has been proved applicable for solving different types of problems from various scientific fields in sequential and parallel computational systems. In Chapter 1, basic mathematical concepts for the numerical solution of sparse linear Least Squares systems are introduced. Additionally, various preconditioned iterative methods for solving linear systems are discussed. Furthermore, an introduction to parallel software environments for modern parallel computer systems and specifically for OpenMP is provided. Moreover, a short literature review for two applications in the field of Traffic Forecasting and Machine Learning focusing on Supervised Learning problems is given. In Chapter 2, a new modified class of incomplete orthogonal factorization based on Givens rotations is introduced. The class of Generic Approximate Sparse Pseudoinverse (GASP) matrices based on Modified row-wise Threshold Incomplete Givens Orthogonalization (mrTIGO) is proposed. The filtering criteria for the Incomplete QR factorization have been modified to improve the quality of the incomplete upper triangular factor, by removing the restriction on the number of nonzero elements per row. The novel GASP preconditioner for overdetermined and underdetermined linear systems is computed, using a “restricted” solution process, based on approximate pseudoinverse sparsity patterns. In Chapter 3, the parallel design of the novel Generic Approximate Sparse Pseudoinverse Matrix, namely ParGASP matrix, following a parallel column-wise decoupled approach for shared memory parallel system is proposed. The ParGASP matrix can then be used in conjunction with Parallel Explicit Preconditioned Conjugated Gradient type methods for solving linear least squares problems. In Chapter 4, explicit preconditioned iterative methods are presented. The Explicit Preconditioned Conjugate Gradient type methods for solving linear least squares problems are introduced. Furthermore, the Explicit Preconditioned Conjugate Gradient Least Squares method in conjunction with GASP matrix for solving overdetermined linear systems is introduced along with its parallel variant for shared memory computer systems. Additionally, the Explicit Preconditioned Conjugate Gradient Method on the Normal Equations method based on GASP matrices for solving underdetermined linear systems is proposed along with its parallel variant for shared memory computer systems. In Chapter 5, the Modified Moore-Penrose conditions, based on Generic Approximate Sparse pseudoinverse technique for overdetermined and underdetermined linear systems are introduced. The sensitivity of the Generic Approximate Sparse Pseudoinverse matrix is studied and theoretical estimates of the iteration matrix for overdetermined and underdetermined linear systems are studied. In Chapter 6, two applications for solving complex computational problems are presented. Traffic forecasting has been extensively studied due to its importance for the design and development of Intelligent Transportation Systems (ITS). An approach for solving large-scale multi-stage traffic forecasting problem is proposed, by using the recently proposed Adaptive Cluster-based Sparse Auto-Regressive (ACSAR) model, leading to overdetermined linear system, which is solved using the Explicit Preconditioning Conjugate Gradient Least Square (EPCGLS) method in conjunction with the GASP matrix. Furthermore, a technique for handling a class of sparse supervised learning problems, specifically focusing on regression, binary and multi-class classification problems is presented. This new Sparse Approximate Pseudoinverse Preconditioning (SAPP) technique, uses the Explicit Preconditioning Conjugate Gradient on the Normal Equations (EPCGNE) method based on GASP matrix for solving underdetermined linear systems. In Chapter 7, numerical results are presented for various model problems in order to assess the performance and the convergence behavior of the proposed schemes for sparse least squares problems along with parallel results. Additionally, comparative results to other well established methods are provided. Moreover, numerical results indicating the applicability and efficiency of the proposed schemes for solving Multi-Step Ahead Traffic Forecasting problems and Supervised Learning Problems, are given along with discussions. Finally, concluding remarks along with future research directions are given.
Degree
thesis:*- Grantor dc:publisher
- Harokopio University
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Lypitaki, Anastasia-Dimitra-Danai
- Λυπιτάκη, Αναστασία-Δήμητρα-Δανάη
Subjects
dc:subject × 20- Προβλήματα Ελαχίστων τετραγώνων μεγάλης κλίμακας
- Υπερκαθορισμένα συστήματα
- Υποκαθορισμένα συστήματα
- Άμεσα σχήματα προσυντονισμού
- Άμεσος γενικός προσεγγιστικός αραιός ψευδο-αντίστροφος
- Large least squares problems
- Overdetermined systems
- Underdetermined systems
- Explicit generic approximate sparse pseudoinverse
- Incomplete QR decomposition
- Μαθηματικά
- Φυσικές Επιστήμες
- Υπολογιστικά μαθηματικά
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Τεχνητή νοημοσύνη
- Mathematics
- Natural Sciences
- Computational Mathematics
- Computer and Information Sciences
- Artificial Intelligence
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/56720