| This thesis covers six combinatorial problems relevant to various problems in scientific computing. The problems were motivated by different scientific computing applications, and the solution techniques used fundamental methods of computer science. We reported both theoretical and practical results for these problems. Our work included complexity analysis and design and analysis of algorithms, as well as implementation and empirical studies.; We first study improving the performance of matrix-vector multiplication by reducing the number of extra load operations. The second problem is one-dimensional partitioning of workload arrays, for which we propose runtime efficient algorithms to find optimal solutions. The third problem is motivated by the discrete ordinates methods for modeling radiation transport, and we propose an easy-to-parallelize algorithm to find strongly connected components. Next, we discuss two communication algorithms to support adaptive computation. The fifth problem is on graph partitioning for complex objectives, where the load is a complex function of subdomains. Finally, we discuss how to exploit flexibility in task assignments to improve load balance.; This thesis highlighted combinatorial techniques in scientific computing as a research field full of interesting problems with real impact. From the scientific computing point of view, our results show that very significant computational savings can be achieved by employing combinatorial techniques. Moreover, the complexity of problems often requires sophisticated combinatorial techniques, and using simple, brute-force techniques may be very inefficient. From the computer science point of view, it is easy to find challenging combinatorial problems to apply or adapt existing theories or develop new techniques for real-world applications. The breadth of this thesis demonstrates the abundance of combinatorial algorithms in scientific computing as a research field. Each of the six chapters of this thesis was motivated by a different application and the solutions employ different solution techniques. Our results, together with the importance of the problems studied, show the impact of our solutions on real-world applications. |
