稀疏算法是一类广泛存在于各类应用中的核心算法。在目前的高性能计算机系统上，稀疏算法的浮点效率经常不到10％，影响了高性能计算机计算能力的发挥。本文在传统应用领域和新兴应用领域分别选择一个典型的稀疏算法一稀疏矩阵向量乘法(SpMV)和介度中心算法(BC算法)，通过这两个算法来研究稀疏算法的并行优化问题。本文的主要工作包括以下几个方面：　　 本文设计了一种精确的细粒度性能分析工具，通过这个工具可以实时读取处理器内部的性能计数器的值，精确获得核心算法导致的处理器事件，如Cache Miss、分支预测、硬件预取等各类事件发生的精确次数。弥补了基于统计的性能分析工具(如：Oprofile)的不足之处。本文详细深入研究了稀疏矩阵向量乘和介度中心算法的性能特征，分析了影响稀疏算法性能的主要因素。通过分析发现，稀疏矩阵向量乘的性能瓶颈主要是由于硬件和算法不匹配导致，介度中心算法的锁同步是影响性能的主要开销。　　 本文在汇编语言层次对稀疏矩阵向量乘法做了细粒度的性能优化研究。通过对指令序列的调整，改变指令序列之间的控制相关和数据依赖关系，优化后的算法在Intel平台和AMD平台分别有20％和5％的性能提高。本文提出了一种具有可变分块结构的稀疏矩阵向量乘算法。在很多应用中，稀疏矩阵具有多个分块模式，传统的分块方法很难为这种稀疏矩阵选择合适的分块大小。本文提出了一种基于矩阵分解的方法，针对这类矩阵做性能优化，优化后的算法在Intel平台和AMD平台分别有35％和45％的性能提高。通过在任务划分和负载平衡上的优化，稀疏矩阵向量乘法的多线程并行优化在主流多核平台上有接近线性的加速比，相对于基于多进程的实现平均有21％的性能提高。　　 本文提出了一种消除锁同步的并行介度中心算法，相对于基于锁同步的最优并行实现，新算法有2～3倍的性能提高。这种消除锁同步的优化方法，可以推广到其他与图相关算法的并行实现中，用来消除锁同步带来的时间开销。本文提出了一种基于稀疏矩阵向量乘的并行介度中心算法，对更大规模网络的分布式并行求解做了初步的探索。