The future of high-performance computing relies on the efficient and scalable use of clusters with symmetric multiprocessor (SMP) nodes and low-latency, high-bandwidth interconnection networks. Current examples of such platforms include Sun Ultra HPC machines, Compaq AlphaServers with Quadrics switches, SGI Origins, and the IBM SP system with SMP nodes. Moreover, the future of NASA missioncritical computing for computational aerosciences relies on the success of computational clusters (e.g., SMP Linux clusters at Goddard Space Flight Center, and large SGI Origin arrays at Ames Research Center). Hardware benchmark results reveal awesome performance rates for each component; however, few applications on SMP clusters ever reach a fraction of these peak speeds. While methodologies for symmetric multiprocessors (e.g., OpenMP [21] or POSIX threads [22]) and message-passing primitives for clusters (e.g., MPI [20]) are well developed, performance dictates the use of a hybrid solution. We present preliminary results of our complexity model and programming methodology that is based hierarchically upon realistic model components for message-passing and for symmetric multiprocessor parallel architectures. The current deployment of teraflops and the future development of petaflops systems will certainly require the exploitation of similar hybrid programming models. Our goal is to validate and refine a core complexity model, efficient primitives and algorithmic libraries needed to support the effective use of SMP clusters for computational aeroscience (CAS) and earth and space science (ESS) codes. In addition, we will show how to design, implement, analyze, and refine algorithms that take advantage of the hybrid programming model and contribute to significant speedups for real computational science problems. These will include some basic combinatorial support tasks used in numerical aerodynamics simulations (e.g., sorting integers for particle-in-cell codes) and selected numerical computations (e.g., fast transforms). These algorithmic kernels exhibit promising performance improvements. Our hybrid programming environment also must support mission-critical high-performance computing applications. Thus, we use real computational aeroscience and Earth and space science codes drive our algorithmic development. These applications include segmentation and classification of remotely-sensed imagery, and navigation, calibration, and registration of terascale data sets, for remote sensing (AVHRR and MODIS) and threedimensional numerical relativity with the CACTUS computational astrodynamics toolkit