-1
$\begingroup$

I have 1600 ASCII files with 1000 lines in each file. Each line has only one entry and is a floating point number e.g. 1.67923. Let's denote the line1 of file1 with L(1,1), line2 of file1 with L(1,2) and so forth to ...L(1,1000). Similarly, line1 of file2 will be L(2,1) and the last line of file1600 will thus be L(1600,1000). My task is to come up with a memory efficient algorithm to compare all lines between each file and the lines within each file. Since, I have 1600 files and 1000 lines in each file, it will take approx. 10^12 calculations. I want to distribute these 10^12 calculations to 1000 serial jobs and run them on a cluster. These first comparisons will look like this:

1. {L(1,1)-L(1,2)}, {L(1,1)-L(1,3)},....,{L(1,1)-L(1,1000)}
2. {L(1,1)-L(2,1)}, {L(1,1)-L(2,2)},....,{L(1,1)-L(2,1000)}
3. {L(1,1)-L(3,1)}, {L(1,1)-L(3,2)},....,{L(1,1)-L(3,1000)}
.
.
. 

Please note that I don't want repetitions i.e {L(1,1)-L(2,1)} = {L(2,1)-L(1,1)}. I need to code this problem in Fortran but any help on a general scheme as to how the problem needs to be approached and divided into multiple jobs will be useful.

EDIT

Each line of these files contains astronomical orbital data (one orbit per line), so I have 1600 files with 1000 lines each, which results in 1.6x10^6 orbits. There is a concept in astronomy called Minimum Orbit Intersection Distance or MOID for short, which measures the closest distance between two orbits. So, I need to calculate the MOID between each pair of orbits. Since we have 1.6x10^6 orbits, it will require almost n^2 calculations, ignoring repetitions (the distance between orbit 1 and 2 is equal to distance between orbits 2 and 1). I already have a fortran subroutine to compute the MOID between two orbits, now the question is what is the most practical way of computing the MOID between each possible pair of orbits. Hopefully, that makes sense!

$\endgroup$
  • 2
    $\begingroup$ Memory storage of the 1.6e6 floating point numbers requires only about 12MB (assuming double precision). Reading these files in is a fairly trivial task that you should be able to figure out by internet searching for some basic Fortran tutorials. Storage of the final 1.6e6 x 1.6e6 results, on the other hand, requires ~19TB of space. What are you actually trying to do with this data? $\endgroup$ – LedHead Jan 7 at 18:07
  • $\begingroup$ Coding this in Fortran would be a mistake. Aside from that do you have an idea of how many differences you expect per file? What are you ultimately trying to accomplish? This is the kind of question where the answer depends strongly on the assumptions made. $\endgroup$ – Richard Jan 7 at 23:46
  • $\begingroup$ It's amazing you can encode an orbit's parameters into one number. But assuming you can, doesn't this problem scream for a sort followed by a comparison of pairs? Or data could be organized into a quad tree with subsequent queries being relatively quick even if there are n^2 of them. $\endgroup$ – Bill R Jan 8 at 4:43
  • $\begingroup$ Perhaps each file contains 1000 points indicating the path of the orbit? It does seem unlikely that you can encode the orbit with a single number. Another question: this means that only a single number is stored for each pair of orbits, yes? $\endgroup$ – Richard Jan 8 at 17:29
  • $\begingroup$ The question title, and much of its text, is misleading. This is really asking about how to compute a large distance matrix. If you are really committed to doing this it's very simple: take a handful of coloured pencils; with a plain lead pencil draw the triangle for the lower half (or upper half) of the distance matrix. With your first coloured pencil colour in both the first 800 rows of the triangle, and the last 800. Take the next pencil, colour in rows 801-1600 and (10^6-1600-10^6-801), repeat. The resulting drawing shows how to decompose the task onto the 1000 processes. $\endgroup$ – High Performance Mark Jan 9 at 9:50

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.