About Us

The Seeds of Rose

In 1982 Carl Ledbetter was a manager at IBM Research when he received a call from his friend and former professor, Evar Nering, Chairman of the Department of Mathematics at Arizona State University. Carl and Evar had written the first solution to Rubik’s Cube three years earlier, and now Dr. Nering was collaborating with the renowned mathematician Albert Tucker, a recipient of the John von Neumann Theory Prize and doctoral advisor to John Nash, the famous Princeton mathematician and Nobel Laureate. Nering and Tucker were writing a book, Linear Programs and Related Problems (published in 1993). They had developed a new technique, called Priority Pivoting, to avoid cycling during a stall in the Simplex algorithm in linear programming. However, they didn’t have sufficient computing resources to evaluate their invention or to prove it was better than the standard method, Bland’s Rule.

Carl had access to the most advanced IBM computer at the time, as well as to one of the first million-pixel screens. He wrote the code to run Nering’s Priority Pivoting algorithm using a trick to simplify the data that was displayed as the program ran. As Carl watched the trial runs with the new method, he noticed something interesting. Although it was just an observation at the time, it became the first step toward the creation of SimpleRose.

Over the course of two weeks, Carl developed a hypothesis for what was going on with the patterns he saw in the Priority Pivoting test. He showed the patterns and what he had learned about what they meant to Nering and Tucker later that year. The three of them together were able to develop the underlying mathematics of the phenomenon. The early version of Rose — Rapidly Optimizing Simplex Engine — began to take shape out of that work. The trio started to work on Rose in their spare time while Carl continued his management career and Evar and Al finished their book.

Introducing Rose

In 1992 AT&T hired Carl as President of their Consumer Division. Part of the mathematics and physics departments of Bell Labs reported to him in that role. Nobel Laureate Arno Penzias was head of Bell labs at the time, Ron Graham was chair of the math department, and Narendra Karmarkar, inventor of the interior point method in linear programming, was also in the math department. These three renowned mathematicians were excited to have a fellow mathematician in an executive management position; they considered him, “One of us.” Carl was the first division president in the history of AT&T who had a Ph.D.

Bell Labs hosted a winter conference between Christmas and New Year’s in those years where colleagues presented interesting research projects that were not part of their work for AT&T. Penzias and Graham invited Carl to present his work on Rose at the 1994 conference, and because Al Tucker lived nearby, he attended the lecture. This was the first time that the algorithm was shown to an audience other than the three inventors.

Carl showed that Rose was far more parallelizable than other methods, including all earlier versions of Simplex and the interior point methods that Karmarkar had pioneered. He also showed that Rose was a fast algorithm that avoided some of the worst-case behavior of tableau methods, and that it also had better numerical accuracy than other algorithms. This was a milestone in achieving the resiliency that the National Labs highlighted in their Exascale Computing Report 10 years later.

Proving Rose

That Rose is embarrassingly parallelizable — and that the parallelism increases as the problem gets bigger, following the Gustafson-Barsis Law speedup curve instead of the Amdahl’s Law curve — is one of Rose’s primary advantages over other optimization solvers. However, 1990s computer architecture did not allow for effective, much less efficient, parallel computing for a communication avoiding algorithm like Rose.

It wasn’t until the 2010s that GPU technology advanced to the point that it could manage massive parallelism. Carl bought three Nvidia 1080 cards, and he and his son Noah built their own parallel computer they named Little Rose to run the new algorithm. They obtained an industry standard benchmark set from Hans Mittelmann at Arizona State University and the Supercomputer Center at Edinburgh University and ran the problems on Little Rose; it failed spectacularly because of numerical instability issues in IEEE 754 arithmetic. They didn’t let that stop them. After another year of work, they could do the entire benchmark set faster and more accurately than any published results. Over the next few years, the US Patent and Trademark Office issued five patents to Evar Nering (4) and Carl Ledbetter (4+1).

Founding SimpleRose

In 2018 one of Carl’s former colleagues, Marti Martindale, encouraged him to build a company to deploy Rose. Together they launched SimpleRose, with Carl as CEO & CTO and Marti as COO. Carl and Marti first met in the mid-1980s when he was hired as CEO of ETA Systems, the supercomputer subsidiary of Control Data, and she led the product management group there. They have worked together on supercomputer development and high-performance computing for decades. Carl and Marti are an impressive team, each bringing their talents and passion to the work.