Space & time efficient sparse matrix transpose
Citation:
Robert Crosbie, 'Space & time efficient sparse matrix transpose', [thesis], Trinity College (Dublin, Ireland). School of Computer Science & Statistics, 2015, pp 322Download Item:
Crosbie TCD THESIS 10609 Space and.pdf (PDF) 149.5Mb
Abstract:
Matrix operations are fundamental to linear algebra and have many important applications in areas such as sinmlation of physical systems, economic modeling, linear optimization and numerical analysis. One of the fundamental operations on matrices is the matrix transpose. In many linear algebra applications the matrices are extremely large and require considerable memory to store. Therefore it is desirable to transpose in-place to avoid creating a new matrix which would double the memory usage. Transposing dense matrices in-place has been studied over several decades, and many good algorithms have been found. An area that has been relatively neglected is that of in-place transpose of sparse matrices - that is, matrices where the value of most matrix elements is zero and are stored in a sparse format. The best previous algorithm requires Θ(nnz + n) time and Θ(nnz + n) additional space to transpose an n x n sparse matrix with nnz non-zero entries.
Author: Crosbie, Robert
Qualification name:
Doctor of Philosophy (Ph.D.)Publisher:
Trinity College (Dublin, Ireland). School of Computer Science & StatisticsNote:
TARA (Trinity’s Access to Research Archive) has a robust takedown policy. Please contact us if you have any concerns: rssadmin@tcd.ieType of material:
thesisCollections:
Availability:
Full text availableLicences: