Fortran 90 +
-- Fortran 90, Fortran 95, Fortran 2000 --
A WEB site on the way to more public domain utilities.
While Fortran 90 and later variants have made life much easier for scientific programmers than Fortran 77, the language still lacks depth in public domain utilities. The following package, ORDERPACK 2.0, illustrates the type of important but uncommon routines needed to complete the Fortran programming environment. ORDERPACK 2.0 performs both conventional sorting and ranking as well as the rarer specialized ordering tasks such as partial sorting, partial ranking, unique sorting, unique ranking, inverse unique ranking, etcetera. These partial sort and ranking routines can greatly accelerate many computations when users need only the m largest or smallest elements out of a n element vector. As an example of the speed, in 100,000 trials of picking the smallest 9 elements out of 500 total elements it took in total only 2.7 seconds for the the 100,000 partial and unique rankings on a 600 Mhz PC using CVF 6.1a. A similar experiment involved 100 trials of simulating a random vector of length 1,000,000 and ranking the 20 smallest elements (keeping duplicates). On a 460 Mhz AlphaStation with Compaq Fortran 90 V5.2, taking care to increase stacksize, partial ranking by itself took 2.3 seconds, i.e. 23 milliseconds per vector.ORDERPACK 2.0 Unconditional, Unique, and Partial Ranking, Sorting, and Permutation Fortran 90 source code.
Note that ORDERPACK 2.0 is F-compatible.
Illustrative ApplicationIn spatial-temporal applications one often wishes to know the nearby observations (say the m closest) subject to having these nearby observations also prior in time to the observation itself. Many of the ways of forming purely spatial neighbors such as those based upon Delaunay triangles do not function well in a spatial-temporal setting. However, partial ranking always works and can function with many more dimensions. Since the number of neighbors, m, is much smaller than the number of observations, n, the partial ranking algorithm saves a great deal of time relative to full ranking. For 7,000 observations, the partial algorithm saves almost a factor of 200 in terms of time over the full algorithm. Finding all the neighbors for 100,000 observations takes less than 8 minutes on a 600 Mhz PC, thus making spatial-temporal methods feasible for large data sets on desktop machines. This application was based upon work supported by the National Science Foundation under Grant No. BSC-0136229. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF). Documentation Complete Application (source code, pc executable code, data, documentation)
Last updated: 2004/01/14
Back to top