Abstract: This paper describes an array-based language-level approach to parallel sparse computation. Our approach is unique due to its separation of sparse index sets from arrays, both syntactically and in the implementation. This design allows users to express their computation using dense array syntax, making the code easier for readers to understand and for compilers to parallelize and optimize. This work is done within the context of Advanced ZPL, retaining its crisp syntax and source-level performance model. Our implementation uses a novel sparse storage format that supports general operations such as arbitrary iteration and slicing. We describe how our compiler automatically optimizes this data structure into more compact forms based on the operations required by the program. We demonstrate our approach using the NAS CG and MG benchmarks, comparing our implementations with the original Fortran+MPI versions in terms of clarity and performance. We present performance results on the Cray T3E indicating that our implementation compares favorably to the hand-coded NAS versions in terms of memory requirements and often surpasses them in terms of execution speed.