Petsc supports both dense and sparse data structures sequential and in parallel; there is support for multiple physical variables per unknown.
The data structures are completely hidden from the user, only accessible through function calls. Creation of the vector and matrix data structures is completely general: any processor can specify elements for any other processor.