19th century math tactic gets a makeover—and yields answers up to 200 times faster

Jun 30, 2014
Johns Hopkins graduate student Xiang Yang, at right, teamed up with Rajat Mittal, a professor of mechanical engineering, to revamp a "useless" 169-year-old math strategy, making it work up to 200 times faster. Credit: Will Kirk/JHU

A relic from long before the age of supercomputers, the 169-year-old math strategy called the Jacobi iterative method is widely dismissed today as too slow to be useful. But thanks to a curious, numbers-savvy Johns Hopkins engineering student and his professor, it may soon get a new lease on life.

With just a few modern-day tweaks, the researchers say they've made the rarely used Jacobi method work up to 200 times faster. The result, they say, could speed up the performance of computer simulations used in aerospace design, shipbuilding, weather and climate modeling, biomechanics and other engineering tasks.

Their paper describing this updated math tool was published June 27 in the online edition of the Journal of Computational Physics.

"For people who want to use the Jacobi method in computational mechanics, a problem that used to take 200 days to solve may now take only one day," said Rajat Mittal, a professor in the university's Whiting School of Engineering and senior author of the journal article. "Our paper provides the recipe for how to speed up this method significantly by just changing four or five lines in the computer code."

This dramatic makeover emerged quietly in the fall of 2012, after Mittal told students in his Numerical Methods class about the Jacobi method. Mittal cited Jacobi's strategy as a mathematically elegant but practically useless method, and then moved on to faster methods and more modern topics. Xiang Yang, then a first-year grad student in the class was listening intently.

Mittal had told his students that Carl Gustav Jacob Jacobi, a prominent German mathematician, unveiled this method in 1845 as a way to solve systems of linear equations by starting with a guess and then repeating a series of math operations over and over until a useful solution appeared.

This video is not supported by your browser at this time.
Simulation data showing significantly faster reduction in solution error for the new Scheduled Relaxation Jacobi (SRJ) method as compared to the classical Jacobi and Gauss-Seidel iterative methods.The equation that is being solved here is the two-dimensional Laplace equation on a 128×128 grid.

By the early 20th century, the method was being used by "human computers," groups of men and women who were each assigned to perform small pieces of larger math problems. A noted mathematician during that era managed to make the method proceed five times faster, but that was still considered rather slow. With the advent of speedier strategies and electronic computers, the Jacobi method fell out of favor.

"It just took so much time and so many computations to get to the answer you wanted," said mechanical engineering grad student Yang. "And there were better methods. That's why this Jacobi method isn't being used much today."

But after learning about the method in Mittal's class, Yang began tinkering with it. He returned to Mittal and proposed a way to make the process of repeating numerical estimates move more efficiently, speeding up arrival at a solution. "Instead of saying that this method has been around for 169 years, and that everyone has already tried to improve it without much success, Professor Mittal told me that he felt my idea was very promising," Yang said, "and he encouraged me to work on it."

Yang spent a couple of weeks honing the updated math strategy, which he and his professor called a "scheduled relaxation Jacobi method." Then the grad student and Mittal began working together on a paper about the work that could be submitted to a peer-reviewed journal, with Yang as lead author.

Now that it has been published and is being shared freely, Mittal expects the modified method to be embraced in many industry applications, particularly those involving fluid mechanics.

For example, when an aerospace engineer wants to test several different wing designs in a computer simulation program, the revised Jacobi method could speed up the process. "I expect this to be adopted very quickly," Mittal said. "Everyone is competing for access to powerful computer systems, and the new Jacobi method will save time. In fact, the beauty of this is that it is particularly well suited for the large-scale parallel computers that are being used in most modern simulations."

Oddly enough, the Jacobi update is not directly related to the doctoral project that grad student Yang is supposed to be focusing on: how barnacles on the side of a ship affect its movement through water. But Yang said his doctoral adviser, Charles Meneveau, another mechanical engineering professor, encouraged him to devote some time to the Jacobi paper as well.

Yang, 24, grew up in China and earned his undergraduate engineering degree at Peking University. The school's dean of engineering, Shiyi Chen, a former Johns Hopkins faculty member, encouraged Yang to continue his studies at the Baltimore campus. The grad student said he's appreciated the faculty support at Johns Hopkins. "Professor Mittal taught me to look at a lot of possibilities with an open mind," he said. "Then, it's been relatively easy to handle my schoolwork. He's the one who inspired me."

Explore further: Engineering student developing traffic forecasts

More information: The journal article may be viewed at: engineering.jhu.edu/fsag/wp-co… _revised_WebPost.pdf

add to favorites email to friend print save as pdf

Related Stories

Recommended for you

Ancient clay seals may shed light on biblical era

Dec 20, 2014

Impressions from ancient clay seals found at a small site in Israel east of Gaza are signs of government in an area thought to be entirely rural during the 10th century B.C., says Mississippi State University archaeologist ...

Digging up the 'Spanish Vikings'

Dec 19, 2014

The fearsome reputation of the Vikings has made them the subject of countless exhibitions, books and films - however, surprisingly little is known about their more southerly exploits in Spain.

User comments : 7

Adjust slider to filter visible comments by rank

Display comments: newest first

Returners
2.2 / 5 (10) Jun 30, 2014
I love discoveries like this.

Sometimes something is "so old that it's new," and that's really cool to me.

In thinking about renewable, I've come to realize that a lot of technology we use is based on ideas which are good in the context they were intended to be working. However, they sort of just replaced old ideas with the electrical systems, without as much thought as I think should have been given for integrating old and new. Now, with energy costs high, people look to old methods to solve the same problem, solar heating, self ventilation, etc, but with modern knowledge and technology added in the mix.

So, finding a way to use an old strategy to solve a problem (this looks a lot like Newton's method too,) is appealing to me.

I used to do "guess and check" methods when I forgot the formulas in school sometimes, and would just work out the answer in that manner.

Solving a 128x128 grid by hand, in any context, would be absurdly stupid though, unless it had very novel properties.
Returners
1.5 / 5 (8) Jun 30, 2014
Like for example, I wrote a php program (and you can do it with Java too) which could work in long decimal numbers, up to 4 gigabytes in size, because it doesn't come standard in any software package. I've actually lost that because it was on my other computer and that one is fried.

I wasn't making a web site, I was just making some toys, including an attempt at a weak, but self-editing a.i.

It was going to result in iterative problem solving as well as developing a "dynamic algorithm memory" not just in normal database entries, but within the code itself....like "muscle memory" or "reflexes." That is solving and remembering problems it had never seen before.

PHP is inefficient for that, but I find certain aspects of the PHP language engine to be easier to work with than the C language. One problem I had is some things are just plain easier to do in PHP, while other things are easier to do in C directly, but a C program can't really self-edit like a PHP, since PHP is interpreted.
Returners
1 / 5 (6) Jun 30, 2014
Our brains seem to use interpreted algorithms and knowledge, but C and C++ are compiled languages, which makes it hard to do the types of things I was experimenting with.

Scripting languages went back to some combination of interpreted and compiled languages. I like interpreted languages because they appear more dynamic and easier to edit and maintain, or so it seemed at first to me, but the "class" and function system in PHP can get out of hand if you have some nesting going on. What I really wanted to do was eventually going to have immense parallelism and nesting. It involved iterative problem solving and attempting to optimize a dynamic algorithm. Create a pointer to a database entry, write that algorithm in that database, as well as a "description" which is some code which identifies to the main program what that code does. In this way, it could "remember" the best version of the algorithm it dynamically wrote, instead of doing it again.
EWH
5 / 5 (1) Jun 30, 2014
"I wrote a php program (and you can do it with Java too) which could work in long decimal numbers, up to 4 gigabytes in size..."

For unlimited precision rational numbers (not decimal, but they can easily substitute) try the free (as in beer) scripting language Frink, which runs on the JVM (any OS, phones, embedded in webpages etc.) and also has a combination of very useful features not found anywhere else such as physical typing (recognizes and converts any units, e.g. "ounce c^2 -> gallon gasoline", also can do currency conversions, including precious metal values, and inflation corrections between different years), time and calendar conversions with unmatched accuracy, number theory functions, interval arithmetic for error bars, human language translation, self-modifying programs, reads webpages as easily as local files, can make dimensioned drawings...
See http://futureboy.us/frinkdocs/ for more
otero
Jun 30, 2014
This comment has been removed by a moderator.
alfie_null
5 / 5 (1) Jul 01, 2014
PHP is inefficient for that, but I find certain aspects of the PHP language engine to be easier to work with than the C language. One problem I had is some things are just plain easier to do in PHP, while other things are easier to do in C directly, but a C program can't really self-edit like a PHP, since PHP is interpreted.

Learn how to use LISP. It will be good for you.

If all you have is a hammer, every problem looks like a nail.
marko
1 / 5 (2) Jul 03, 2014
The difference between math and computer science is that math takes a complex problem and solves it - while programmers take a solution and then make it into a complex problem.
Returners
1 / 5 (2) Jul 06, 2014
The difference between math and computer science is that math takes a complex problem and solves it - while programmers take a solution and then make it into a complex problem.


Not really.

I have a cousin who struggled in high school math, but did very well in computer related technical schools. eventually he got this just where he stayed for about 3 years, then another, then moved to his third where he now makes 80k per year...Never did graduate from technical school, because he couldn't afford to do so, at the time, and just started work for his first major employer while he had been in school, but because the load became so much he just quit the tech school. Why pay when he already had the job?

A few years later, he's making twice the average in his field, and doesn't have a degree.

Computer programs are much more complicated than virtually any "real world" math problem, because you are making decisions; sometimes you're making decisions about things you don't know yet.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.