Paralel seyrek matris-vektör çarpımı ve dolaylı yöntemler

parse matrix-vector multiply (SpMxV) operations are in the kernel of manyscientific computing applications. Therefore, efficient parallelization of SpMxVoperations is of prime importance to scientific computing community. Previousworks on parallelizing SpMxV operations consider maintaining the load balanceamong processors and minimizing the total message volume. We show that the to-tal message latency (start-up time) may be more important than the total messagevolume. We also stress that the maximum message volume and latency handledby a single processor are important communication cost metrics that should beminimized. We propose hypergraph models and hypergraph partitioning methodsto minimize these four communication cost metrics in one dimensional and twodimensional partitioning of sparse matrices. Iterative methods used for solvinglinear systems appear to be the most common context in which SpMxV operationsarise. Usually, these iterative methods apply a technique called preconditioning.Approximate inverse preconditioning—which can be applied to a large class ofunsymmetric and symmetric matrices—replaces an SpMxV operation by a se-ries of SpMxV operations. That is, a single SpMxV operation is only a piece of alarger computation in the iterative methods that use approximate inverse precon-ditioning. In these methods, there are interactions in the form of dependenciesbetween the successive SpMxV operations. These interactions necessitate parti-tioning the matrices simultaneously in order to parallelize a full step of the subjectclass of iterative methods efficiently. We show that the simultaneous partitioningrequirement gives rise to various matrix partitioning models depending on theiterative method used. We list the partitioning models for a number of widelyused iterative methods. We propose operations to build a composite hypergraphby combining the previously proposed hypergraph models and show that par-titioning the composite hypergraph models addresses the simultaneous matrixpartitioning problem. We strove to demonstrate how the proposed partitioningivvmethods—both the one that addresses multiple communication cost metrics andthe other that addresses the simultaneous partitioning problem—help in practice.We implemented a library and investigated the performances of the partitioningmethods. These practical investigations revealed a problem that we call messageordering problem. The problem asks how to organize the send operations to min-imize the completion time of a certain class of parallel programs. We show howto solve the message ordering problem optimally under reasonable assumptions.Keywords: Sparse matrices, parallel matrix-vector multiplication, iterative meth-ods, preconditioning, approximate inverse preconditioner, hypergraph partition-ing.