In this paper we present a parallel formulation of a graph partitioning and sparse matrix ordering algorithm that is based an a multilevel algorithm we developed recently. Our parallel algorithm achieves a speedup of up to 56 on a 128-processor Cray T3D for moderate size problems, further reducing its already moderate serial run-time. Graphs with over 200,000 vertices can be partitioned in 128 parts, on a 128-processor Gray T3D in less than 3 seconds. This is at least an order of magnitude better than any previously reported run times on 128-processors for obtaining an 128-partition. This also makes it possible to use our parallel graph partitioning algorithm to partition meshes dynamically in adaptive computations. Furthermore, the quality of the produced partitions and orderings are comparable to those produced by the serial multilevel algorithm that has been shown to substantially outperform both spectral partitioning and multiple minimum degree.