Slashdot Mirror

Greengard and Rokhlin's Fast Multipole Method (FMM) algorithm computes an approximation for the sum total of the interactions between all pairs of elements out of a large group.

For instance, in astrophysics simulations, one quantity that needs to be computed is the total force on a star that results from the gravitational attraction from each of the other stars. If you have to do this computation for each star, then the total ammount of computation required grows as N^2, given N total stars.

This is where the name "The N-body Problem" comes from.

The FMM algorithm essentially models distant groups of particles (stars) as a single mathematical object and by using other fairly complex operations and representations, reduces the overall complexity from N^2 to N.

The importance of this algortihm comes from the fact that in many different types of scientific simulations (astrophysics, molecular modeling, computational fluid dynamics, etc.) the N-body computation was the limiting factor in the performace of these algorithms. Use of FMM and similar algortihms has reduced the overall simulation times by orders of magnitudes for large systems, allowing simulations that once required CPU-decades to be completed in CPU-months.

There are several good sources of FMM material on the web. You can try:

Mario's Nbody resources

More Nbody

Leslie Greengard's page

And of course, I'll have to plug our research group page at Duke

Hope this helps

-bill

I really don't care for their choices at all. A lot of them are more like general approaches than algorthms, and I'm not at all sure they are the most influential. I think they are supposed to be "the cleverest of the common fancy methods"

Simple algorithms for common problems are much more widely used, and have far more impact and influence, but try telling *them* that!

I hope these links help. (Warning: many are technical) If anyone has personal favorites that are less dry than many of these, please post!.

10. 1987: Fast Multipole Method. A breakthrough in dealing with the complexity of n-body calculations, applied in problems ranging from celestial mechanics to protein folding. [Overview] [A math/visual approach]

9. 1977: Integer Relation Detection. A fast method for spotting simple equations satisfied by collections of seemingly unrelated numbers. [Nice article with links]

8. 1965: Fast Fourier Transform. Perhaps the most ubiquitous algorithm in use today, it breaks down waveforms (like sound) into periodic components. Everyone knows this one (or should) [Part II of my personal favorite FFT and wavelet tutorial]

7. 1962: Quicksort Algorithms for Sorting. For the efficient handling of large databases. [Definition][Basic Method][Mathworld][More technical explanation][A lecture with animations and simulations]

6. 1959: QR Algorithm for Computing Eigenvalues. Another crucial matrix operation made swift and practical. [Math] [Algorithm

5. 1957: The Fortran Optimizing Compiler. Turns high-level code into efficient computer-readable code. (pretty much self-explanatory) [History and lots of info]

4. 1951: The Decompositional Approach to Matrix Computations. A suite of techniques for numerical linear algebra. [matrix decomposition theorem] [Strategies]

3. 1950: Krylov Subspace Iteration Method. A technique for rapidly solving the linear equations that abound in scientific computation. [History] [various Krylov subspace iterative methods]

2. 1947: Simplex Method for Linear Programming. An elegant solution to a common problem in planning and decision-making. [English} [Explanation with Java simulator] [An interactive teaching tool

1. 1946: The Metropolis Algorithm for Monte Carlo. Through the use of random processes, this algorithm offers an efficient way to stumble toward answers to problems that are too complicated to solve exactly. [English] [Code and Math] [Math explained]

The truth about gravity is very interesting. However, my knowledge cannot be passed on to you because my life holds greater value than the dissemination of this info (from my point of view). I apologize for my selfishness, but must point out that this what society has taught me.

Search here.

It's available at http://www.math.duke.edu/~yu/wreq/.

It's good in that you can see past queries along with answers posted by the support staff(almost like a self generating FAQ).

wrighty

void russian_roulette(void) { char *target; strcpy(target, "bullet"); }

If history is any indication, yes. I scanned this off the sleeve of Thin Lizzy's 1976 album Jail Break. Once the music companies figure out how to make money off MP3, they'll be the biggest defenders of the format, just watch. It's just like the movie industry and VHS.

-Flerg

Hmm. In many peoples' minds this idea was discredited decades ago.

"Like an accumulation of genetic errors, or noise in analog duplication, each successive Bert Bert was less of an image of Quater."

Clearly Bert Bert forgot to evolve by natural selection.

Your premise that we cannot create something better then ourselves is disproved by the whole history of technology. A stone axe cuts better than my hand does. A bicycle travels faster than I can run. A computer may one day be more intelligent and more conscious than (even:) I am.

Answer: That depends on who has more experience. The one who has actually done a break job ranks alot higher than the one with a framed Ford certificate on the wall. BOTH are just as capable of making mistakes.

There's something to be said for training, but there's much more value in experience.

I, for example, taught myself to program C. Yes, I took programming courses, but I was mostly just setting there waiting for the instructor to get on with it. (I also took BASIC, FORTRAN, PASCAL, and C++ courses from high school onwards.) Having taught FORTRAN labs I can say without any doubt, certification ("book learning" or "in theory") is no substitute for actual experience ("in practice").

In fact, most of what I know I learned on my own. I would expect this to be true of many slashdoters. (I could quote 7th grade SAT scores, but I won't. [Part of the Duke University Talent Identification Program back in 1985, I took the SAT for the first time in the 7th grade. TIP still exists; my nephew is now part of the program :-)]

Answer: That depends on who has more experience. The one who has actually done a break job ranks alot higher than the one with a framed Ford certificate on the wall. BOTH are just as capable of making mistakes.

There's something to be said for training, but there's much more value in experience.

I, for example, taught myself to program C. Yes, I took programming courses, but I was mostly just setting there waiting for the instructor to get on with it. (I also took BASIC, FORTRAN, PASCAL, and C++ courses from high school onwards.) Having taught FORTRAN labs I can say without any doubt, certification ("book learning" or "in theory") is no substitute for actual experience ("in practice").

In fact, most of what I know I learned on my own. I would expect this to be true of many slashdoters. (I could quote 7th grade SAT scores, but I won't. [Part of the Duke University Talent Identification Program back in 1985, I took the SAT for the first time in the 7th grade. TIP still exists; my nephew is now part of the program :-)]

In my OS class (and at other schools like UC Berkeley, Duke, and Harvard) we used a package called NachOS. It runs on a MIPS emulator, and you write large chunks of the OS yourself. We had to write processes, system calls, filesystems, VM, schedulers, applications for the OS (the shell was just 5% of assignment 2). The final assignment is to write a couple different schedulers or other subsystem, then performance analyize the hell out of it, which was really interesting.

Granted this course has a reputation for being WICKED hard. The whole OS is multi-threaded etc etc, so you have to deal with all the fun race condition issues just like a real OS. Running on a simulator makes life much better for a couple of reasons. 1) crash/rebuild/restart/debug cycle is MUCH FASTER. 2) debugging real kernels w/o having two machines (for serial debugging) is not fun, plus you've got to have the machines for the students, which can be a pain. 3) come on, device drivers aren't the _interesting_ part of the OS, so using a system where thats already done is more useful.

I liked doing this better than what other people here have suggested. I think just writing a device driver is kinda silly. It's a reasonably straight forward project, not really a good thing to do in an OS course, having students working with all the important OS components is much more useful. Starting with Linux is not a very good idea because of the large code base, and from what I've seen it's not really the best code for students to read. I would recommend one of the BSDs if you really want to go with the whole OS paradigm, especially FreeBSD when McKusick comes out with "The Design and Implementation of the FreeBSD Operating System." A second OS course or a Graduate level one is a better place to have students dive into a real OS, at that point you know the background theoretics of OS work, and you've written a fairly large code base of your own. Then it becomes much easier for students to dive into a real OS and do some research.

For books I'd say the Tanebaum book (already mentioned here) and the 4.4BSD book are very good.

Yes, but not me. I took a graduate class at Duke University from someone who had been Knuth's graduate student at Stanford.

This has to be quick, but- for anyone who uses Linux, legOS is not at all difficult to setup or maintain. John Knudsen is a good guy, but he (and the target audience) are windows users. If you can get RH running, you can get legOS running. It is easily the best way to use the Mindstorms from Linux. Check out the homepage or my HOWTO.
~luge (use it before you criticize, guys...)

... Citizens of the Universe, Recording Angels. We have returned to claim the Pyramids. Partying on the Mothership. I am the Mothership Connection.

The Truth is Out There!

"Unfortunaty when the mothership does land, George Clinton and Bootsy Collins will be the only ones aboard."



For the record,

Bigz

... Citizens of the Universe, Recording Angels. We have returned to claim the Pyramids. Partying on the Mothership. I am the Mothership Connection.

The Truth is Out There!

"Unfortunaty when the mothership does land, George Clinton and Bootsy Collins will be the only ones aboard."



Can't get my password,

Bigz

In that article, Linda George, a professor of sociology, states that her claim of intellectual property stems in part from the 'spin' she puts on the topic. Now, if that's her intellectual property, I frankly don't want it--I don't want spin; I want facts. Specifically, I want a clear, well-presented, thorough summary and analysis of the material.

But that's an interesting point in itself. Other people argued that notes are a summary of a creative process, analogous to a review of a concert (IANAL and don't know the legal terminology). Ideally, though, a lecture is itself a summary of a series of creative events (specifically, the research, the literature, whatever). It's the review of the concert, not the concert itself. Those reviews are copyrightable, and if you reprint all or part of it without permission, you've violated that copyright.

I don't necessarily think that that's what the students are doing (maybe they're reviewing the reviews), and, in fact, I don't think the professors should be able to claim IP rights to their lectures. When I prepare a lecture and draw on materials I learned in others' lectures, have I stolen IP? When I design a research project using information I learned in class, have I violated IP rights? What if I put up a webpage for my lab and it uses some information I learned as an undergrad? IMHO, defining a professor's lecture as IP dangerously restricts the free flow of information.

Perhaps the universities recognize this issue as a problem (because it encourages laziness and allows people to get information without paying for it) and are merely choosing a course of action that they think will work.

--leighton

... and so that I can be /.ed:
A picture of 5 Mindstorms, which use reinforcement learning to learn to push trailers around a floor without jackknifing. I actually have access to 7, so if anyone has any suggestions on what to do with all of them...
~luge

Yeah, I figure I'm one of the luckiest guys in geekdom- I've spent the last two semesters getting class credit to play with legos, and got paid to do it over the summer. They are definitely worth the investment- the purest joy I've ever seen college kids have *in class* was CPS196 opening all of their kits on the second day of class. Check out the class page for links and pictures.
~luge

Actually, I was wondering if it weren't related to the Gaussian Orthogonal Ensemble (GOE) distribution, which was a result of much of Wigner's work pioneering Random Matrix Theory (RMT) decades ago.

Mathematically, the GOE distribution characterizes the eigenvalues of a Gaussian distribution of orthogonal matrices containing random elements. (Forgive me if I've got the math a bit wrong; I'm a physicist by trade...)

Physically, the GOE distribution has been popping up in increasingly many physical systems for a while now. Years ago (maybe by Wigner himself? not sure) it was noticed that the energy level spacings of atomic nuclei have statistical properties consistent with the GOE distribution. Some time later, people fooling around with microwave cavities began seeing these distributions as well. The quantum dot folks have also run into the GOE distribution, I believe.

The GOE distribution seems to provide a good test for broken symmetries in a system. As a system's symmetry is gradually broken by, say, shaving off a corner of a piezoelectric crystal, the statistics followed by the eigenvalues (in this example, the resonant frequencies) gradually shift from GOE to Poisson, the latter which characterizes the eigenvalues of a truly random system.

Now, two really cool things about the apparent universality of the GOE distribution are:

• The distribution is parameter-independent, and does not contain any information about the system being analyzed. I can glom together energy level data from many different nuclei and still obtain the same GOE distribution.
• There appears to be a connection to chaos.

Neat, chaos! Well, sort of. If you take a classically chaotic system, say, a Sinai billiard, and quantize it (solve the Schroedinger equation), time after time you will discover that the eigenvalues of the quantized system have these nice statistical properties that happen to fall out of RMT, namely, the GOE distribution.

So does that mean all quantum systems that follow GOE statistics are chaotic? No. In fact, it's difficult to define what "chaos" really means for a quantum system that has no classical analog. But it implies there's a connection, it certainly is fun to think about, and perhaps continued research will reveal a deeper universal phenomenon at work. I wonder if these researchers haven't taken another step in that direction.

Dang, I wish I had something up on the web about how my research relates to all this... well, you can email me.

Cute. But you could at least include one link. How about something about the monoliths or 2001 concepts or 2001 in Clarke's works or mention that the book explains a lot of things which a narrator in the movie would have mentioned.

Since the article is pretty short on details, I thought I'd throw out some notes:

1) The Lego uses a Hitachi H8-300 chip, which is a target for gcc, so compiling code for the chip is merely a matter of rebuilding gcc as a cross-compiler.

2) Strictly speaking, LegOS is not an OS but a library, which you compile along with your actual code to give you OS-like features: threading, time management, etc. It also frees you from lego's arbitrary limit on variables (only 32! with no data structures! eww...) and other such problems.

Umm... that's all the geek info I can think of off the top of my head. URLs:
The Official LegOS homepage.
LUGNET, which is a discussion area for all types of lego stuff. the robotics list there serves as the main discussion area for LegOS development and use.
The Internals page. Already mentioned here on /. by Russ Nelson.
EmuLegOS. An emulator for LegOS. Gives you a yellow box on your screen, just as if you owned a Lego brick yourself :) Also very useful for debugging.
My HOWTO. More or less the official documentation. Enjoy.

Good luck- help Lego back into the black-
luge

He was mean, though! Seriously, the sig was a bit old and needed replacement; that was just my excuse. If you want to see it again, by all means.

He did go through the trash learning how to program! He said so himself!


It used to be my sig on Slashdot:

You've got to be willing to read other people's code, then write your own, then have other people review your code.
-- Bill Gates

So I made a webpage explaining it (it has a lot of typos since I made it in 5 minutes). See Gates himself admit that he went through the trash looking for source code here

Contrary to some other posts on the list, you can use the RCX with Linux. Markus Noga and some others have written replacement firmware, which allows full control of the motors, IR, and sensors. It's in C, with C++ support. Check it out at
http://www.multimania.com/legos/.
there is also a mailing list/bulletin board system at:
http://www.lugnet. com/news/display.cgi?lugnet.robotics.rcx.legos
Finally, I've written a brief HOWTO (still very, very beta) at:
http://arthurdent.dorm.duke. edu/legos/HOWTO/HOWTO.html
It's not much, but hopefully between the three of those the rest of you can figure out where to start.
~luge

Done. here . Hope you don't mind the png file.

http://kedem.cs.duke.edu/CipherFlow/ index.html
Looks like no new mathematical things here--just applying SIMD to cryptanalysis. Kewl idea, but no new algorithmic problems.