Summary of the impact

Maple is a major commercial computer algebra system, with millions of users worldwide. It is used in many industrial applications, covering diverse sectors including automotive, aerospace and defense, electronics, energy, financial services, consumer products, entertainment, basic research and teaching. Research by Davenport's team at Bath, in collaboration with the University of Western Ontario, has led to algorithmic advances that have been incorporated in recent releases of Maple. These advances mean that Maple can solve systems of equations it could not previously solve, give completely accurate solutions to systems it could previously only approximate, and can present the solutions to the user in an improved manner.

As well as including code written at Bath directly in Maple, MapleSoft have deployed a Senior Developer to integrate the work of Davenport's team closely into the Maple system. These solution algorithms are now transparently available to all users of Maple. MapleSoft themselves have used the solution algorithms in an industrial application in a consultancy project with a major Japanese automotive manufacturer.

Underpinning research

There are three related themes to the research, which was conducted by Bradford (L/SL at Bath throughout) and Davenport (Professor at Bath throughout), in collaboration with the University of Western Ontario (Corless, Jeffrey, Moreno Maza, Watt), and more recently Peking University (Xia), USNA (Brown) and Macquarie (McCallum).

The first is the polynomial geometry of the reals, with [1] giving a key theoretical result and [2] more algorithmic results, demonstrating how to use the notion of triangular decomposition to analyse semi-algebraic systems of equations and inequations over the real numbers. [2] shows that triangular decompositions can be computed in exponential time under certain circumstances (vs. the worst-case doubly exponential complexity) and gives a collection of experimental results. [3] describes how to deliver these algorithmic results in a manner that the user can appreciate.

The second is the vexed (at least since 1971) question of simplification of algebraic expressions in computer algebra. Why is √(1 - x²) = √(1 - x) √(1 + x ),but √(x²- 1) ≠ √(x + 1) √(x - 1 ) (try𝑥=−3)? Here we see a breakthrough in [4 and 5], with the development of a simplification algorithm that is always correct, by taking proper account of the branch cuts of the expressions being manipulated. This idea was taken further in the EPSRC-funded work of [6]; key examples from this paper were used in the prize-winning demonstration of [2] and its successors at ISSAC 2011.

The third is the extraction, and optimal description, of the branch cuts of the elementary functions [7, ongoing]. A partial answer to the question posed above is that the branch cuts of {√(x²- 1),√(x + 1) ,√(x - 1 )} partition the complex plane, whereas the cuts of the other identity above do not. Finding and describing these branch cuts, with the Maple implementation, is described in [8].

References to the research

* marks the outputs best indicative of the quality of underpinning research

Details of the impact

Maplesoft is an innovative software company with over 120 employees that has been developing and marketing mathematical software for over 25 years, starting as a spin-out from the research group at U. Waterloo (Canada). Their flagship product, Maple, is used in universities and industrial research institutes around the world, and has achieved an excellent reputation in the academic community. It is a significant piece of software, retailing at around £1,000 per individual licence. Maple technology is employed by several million users world-wide, in many areas of science and engineering. Maple is the computation engine used by Maplesoft's engineering simulation product MapleSim, which provides engineers with physical modelling tools to analyze, test, improve, and optimize designs before actually building the physical system.

According to a Maplesoft press release [9] Maple has customers "covering diverse sectors including automotive, aerospace and defense, electronics, energy, financial services, consumer products, and entertainment, basic research and teaching. Over 90% of advanced research institutions and universities worldwide, including MIT, Stanford, Oxford, the NASA Jet Propulsion Laboratory, RWTH Aachen, the University of Stuttgart, and the U.S. Department of Energy, have adopted Maplesoft solutions to enhance their education and research activities." Customers include Ford, BMW, Bosch, Boeing, NASA, Canadian Space Agency, Canon, Motorola, Microsoft Research, Bloomberg, and DreamWorks.[10]

One of the major uses for computer algebra systems is solving systems of equations. Such systems may have solutions in both complex numbers and real numbers, and in many applications one is only interested in the real solutions, and moreover one may wish to know how the existence of such real solutions depends on parameters. Since 2010, Maplesoft has been incorporating the research of Bradford, Davenport and colleagues into their product. As a result, Maple is now able to:

• Correctly solve systems of equations when it previously returned a warning, and few, or sometimes no, actual solutions;
• Correctly handle correlation between solutions, e.g. instead of saying x=±√2, y=±√2 (four solutions), it can now say x=±√2, y=-x (two solutions);
• Extend this to real-only solutions, of great practical importance to engineers;
• Correctly handle case analysis when the number of real solutions depends on the parameters.

As explained by the Director of Research at Maplesoft [11]

"The team have contributed work to our flagship product, the computer algebra package Maple, which in turn is used by our engineering simulation product MapleSim and teaching and assessment product MapleTA. Bath's first contribution was in Maple 14 (released in Spring 2010) with contributions to each subsequent release including our most recent, Maple 17 (released Spring 2013).

Davenport contributed to algorithms for solving parametric polynomial equations in real variables. This led to solutions which were not previously available displayed in an optimal way to the user. We valued this work to the extent that our Senior Developer embedded it into the core tools for solving polynomial systems. This means that users can benefit from the new algorithms when appropriate without having to have knowledge of the mathematics involved, or even knowledge that the algorithm exists. In relation to this Davenport assisted with the development of a new output format for displaying such solutions which has since found use elsewhere in Maple."

Adoption timeline

The interaction of the Davenport team with Maplesoft developed from Davenport's collaboration with researchers at U. Western Ontario, which in turn grew from his Visiting Professorship at U. Waterloo, the birthplace of Maplesoft, in 2009.

The work in [3] made its appearance in Maple 14 (2010) and was a major feature of the Maple 14 launch at ISSAC 2010 (Munich). Part of the work in [2] appeared in Maple 14, and the rest, and some successor work, in Maple 15 (2011). Marc Moreno Maza's demonstration of this technology won the "Distinguished Software Demonstration" award at ISSAC 2011
(http://www.sigsam.org/awards/). The interactive help functions in Maple 15 [12] refer to [2] as a primary reference in the documentation of the RealTriangularize function. Further work from [2]'s successors, some currently unpublished work, and work from [7], has been incorporated in Maple 16.

Further work building on [7] (code developed at Bath funded by EPSRC and described in [8]) has appeared in Maple 17, which was released in March 2013. In an announcement to Maple beta-users of 27/1/2013, Maplesoft's Research Fellow described new features as "very nice work by the group of Prof. James Davenport [...] in collaboration with us at Maplesoft." [13] This means that Maple 17 gives explicit (rather than merely implicit) and more accurate information on branch cuts than its predecessors. For example, when querying the branch cuts of log (-√x), previous versions indicated branch cuts when -√x is negative, from which the user has to infer  x > 0, while Maple 17 returns this directly, along with the cut x < 0 (due to the √x ) which had been missed before. The new code also provides visual output as well as algebraic descriptions.

Usage

The new solving algorithms have already found industrial application. Maplesoft's Director of Research states that "In 2012, we were able to employ the parametric real-solving algorithms developed by Moreno Maza and Davenport and their students for an industrial application that was done as part of a multi-year research and consulting project about symbolic methods in control theory for a Japanese automotive manufacturer." [11]

Thanks to the work of a Maplesoft Senior Developer, as described by their Director of Research above, Maple 17 also integrates the above features into the mainstream: users asking Maple to solve systems of equations benefit from the improved functionality transparently [14]. The potential reach of this work therefore includes all users of Maple and MapleSim who require real solutions to systems of equations.

Sources to corroborate the impact

[9] Maplesoft press release detailing levels of usage of Maple:
http://www.maplesoft.com/company/publications/articles/view.aspx?SID=35294

[10] Maplesoft press release
http://www.maplesoft.com/company/publications/articles/view.aspx?SID=145941

[11] Director of Research, Maplesoft Inc. Statement on file.

[12] Maple help pages http://www.maplesoft.com/support/help
(e.g. /Maple/view.aspx?path=RegularChains%2fRealTriangularize for Bath contributions, and Maple/view.aspx?path=RegularChains/SemiAlgebraicSetTools/CylindricalAlgebraicDecompose For developments of [3])

[13] New in FunctionAdvisor in Maple 17: branch cuts of expressions and their plotting.
Announcement to Maple Beta Users forum, 27/1/2013.
http://beta.maplesoft.com/maple/viewtopic.php?p=60323#60323 (maple beta-users login required; copy retained on file at U. Bath.)

[14] Maple "What's New" pages
http://www.maplesoft.com/support/help/Maple/view.aspx?path=updates%2fMaple17