Compact Computer Algebra

Some ways to implement computer algebra compactly include:

• Exploiting the evaluation-interpolation homomorphism to avoid even parsing, such as in Picomath.
• Using an unavoidably-embedded implementation language and interface toolkit like such as Java or Basic, as was done for PicoMath and Calculus Demon.
• Using contiguous storage as a peek-a-boo stack to avoid garbage collection and pointer space overhead, such as in Calculus Demon and TI-Math-Engine.
• Using a lean Prolog or Lisp subset interpreter together with tail-shared byte-code or cdr-coding to reduce program size, such as in muMath and Derive.

[presentation slides (PDF 1.2MB) ]

AsirPad is a computer algebra system with a Pen-based interface on PDA. User can input mathematical expressions by hand and execute calculations on it. The computational engine of AsirPad is Risa/Asir, and the communication protocol is OpenXM. The handwriting recognition algorithm used in AsirPad is the same as InftyEditor that is a mathematics typesetting tool.

In this talk, I would like to introduce the handwriting recognition algorithm, and explain the design of the user interface of AsirPad.

[presentation slides (PDF 2.3MB) | demos (ZIP 32MB) ]

In 1984 when David Stoutemyer compared different data structures for polynomials, he concluded that the recursive representation (used by Derive, Macsyma, REDUCE, Pari, and Trip) was better overall than the distributed representation (used by Magma, Maple, Mathematica, and Singular) and, surprisingly, that recursive dense (used by Pari) was clearly best overall. In 2003, when Richard Fateman compared many computer algebra systems on polynomial multiplication, his benchmark confirmed Stoutemyer's conclusions. Pari and Fateman's own implementation of recursive dense were the fastest systems on his benchmark. So is recursive dense still the best choice in 2008? Does the emergence of 64 bit computers have any implications on this choice? What about the algorithms? Have we missed anything?

In this talk we take another look at the sparse distributed representation with terms sorted in a monomial ordering. Our algorithms for polynomial multiplication and division use an auxiliary data structure, a ``chained binary heap''. Using a heap for polynomial multiplication was first suggested by Stephen Johnson in 1974 and implemented in the ALTRAN system. But the idea seems to have been lost.

In the talk I would like to first show Maple's distributed data structure, Singular's distributed data-structure, Trip's recursive sparse data structure and Pari's recursive dense data structure, and describe the algorithms that these systems use for polynomial multiplication and division and look at their space efficiency. Second I will explain how we can use a binary heap to multiply and divide polynomials using very little auxiliary storage and in such a way that zero garbage is created. Third, I will present our distributed polynomial representation. Finally, I will present benchmarks showing that heaps are very good for sparse and dense multiplication and division. Our timings are much faster than Pari, Magma, and Singular. What we have found is that as we optimize for space, and promote sequential memory access, we generally get increased performance.

[presentation slides (PDF 680KB)]

SpaceTime 3.0 powered by MobileCAS is cross-platform computer algebra software for computers and mobile devices. Originally developed for the Pocket PC, MobileCAS was built from the ground up for mobile devices. The result is a highly portable and light weight computer algebra system that uses less than 500KB of storage space.

This talk will discuss the evolution and development of MobileCAS in C++ using techniques such as inheritance, polymorphism, templates, operator overloading and the Standard Template Library (STL). The new built-in programming language in MobileCAS will also be discussed and the way it lets users create truly portable code.

SpaceTime 3.0 supports Windows, Mac, Pocket PC, Windows Mobile Smartphones, Palm OS and is in development for Linux and iPhone. All attendees will receive a free copy of SpaceTime 3.0 from SpaceTime Mathematics for any platform of their choice. You can visit the website for more information about SpaceTime 3.0 and related software.

When space is short, it helps to do two things with one set of code. In this talk I shall describe a generalization of LU matrix factors for non-square or rank-deficient matrices. With this factoring the Moore-Penrose inverse can be computed with several matrix products and one inverse. In addition, using a fraction-free form of the LU factors allows us to compute the Moore-Penrose inverse in a fraction-free manner.

[presentation slides (PDF 500KB) ]

In [4], we showed simple algorithms to compute comprehensive Groebner systems (CGS) and comprehensive Groebner bases (CGB). We call them the Suzuki-Sato algorithms. Other known existing software packages to compute CGS or CGB are Redlog (Weispfenning) [1] and DISPGB (Montes) [2].

One of the main advantages of our software is on its simplicity. In fact, our algorithms require only computations of reduced Groebner bases in a polynomial ring over a ground field. This simplicity makes it extremely easy to implement our algorithm on many computer algebra systems. In fact, I have implemented them on Risa/Asir [3] , Singular, Maple, and Mathematica.

The simplicity of our algorithms also gives us the second advantage. Since the main portion of our software is the computation of usual reduced Groebner bases, we can directly use the performance of the built-in Groebner bases computation package. As a consequence, our implementation on Risa/Asir which has a fast Groebner bases computation package is much faster than the others in case we do not have many parameters. It can be run even on a small PDA machine such as SHARP Zaurus.

Furthermore, it is not so hard to implement computation of reduced Groebner basis by Java. So implementation of CGS by Java is not difficult by the same reason. I have implemented it and it works on smartphone such as a Symbian OS phone which have JVM of Java ME CDC, e.g., SonyEriccsson M600i. In the demonstration, I give a brief description and a demonstration using them.

References
[1] Dolzmann, A. and Sturm, T. (1997). Redlog: Computer algebra meets computer logic, ACM SIGSAM Bulletin, 31, 2, 2-9.
[2] Manubens, M. and Montes, A. (2006). Improving DISPGB algorithm using the discriminant ideal, J. Symb. Comp. 41, 1245-1263.
[3] Noro, M. and Takeshima, T. (1992). Risa/Asir – A Computer Algebra System. International Symposium on Symbolic and Algebraic Computation (ISSAC 92), Proceedings, 387-396.
[4] Suzuki, A. and Sato. Y. (2006). A Simple Algorithm to Compute Comprehensive Groebner Bases Using Groebner Bases, International Symposium on Symbolic and Algebraic Computation (ISSAC 2006), Proceedings, 326-331.

[presentation slides (PDF 750KB) ]

This work presents recent results in the representation of digital ink and handwritten character recognition. We have been motivated by the problem of recognizing handwritten mathematical characters, where there are multiple similar characters using a small number of strokes and for which new techniques must be devised.

The usual representation of digital ink is as a stream of (x,y) points sampled along the ink trace curves, possibly with additional coordinates for pressure, pen angles and so on. To represent these ink traces more compactly they are often ``resampled'' to reduce the number of points. Recognition is typically performed using hidden Markov model or support vector machine techniques, based on features extracted from the coordinate curves. These methods require that the entire curve trace be written before recognition commences. This means that recognition on a pen-enabled device, such as a Tablet PC or PDA, typically proceeds in alternating phases of having the processor mostly idle while collecting input and having the user wait while characters are being recognized.

We take a different point of view and ask to what degree it is possible to do useful computation as the digital ink is being written. The initial application is to the problem of mathematical handwriting recognition, where characters are typically written individually and segmentation is not an issue. Our approach is also applicable to other real-time problems such as recognition of other printed handwriting, recognition of entire cursively written words and other classification problems for curves.

Earlier work has shown how the coordinate curves X(t) and Y(t) for handwritten characters can be modelled succinctly by truncated Chebyshev series and that the series coefficients can be used to classify characters and for recognition. Rather than describing a digital ink trace by a few hundred coordinate values, instead a visually indistinguishable curve can be modelled by a just a few series coefficients. A secondary benefit of this representation is that the geometry of these curves can be analyzed by powerful analytic techniques rather than ad hoc numerical techniques.

The present work starts with a similar approach, but uses a different functional basis that allows computation as the curve data is received. The basic idea is to integrate moments of the coordinate curves in real time as the stroke is written and then to construct the coefficients for a Legendre series representation of the size-normalized curves in constant time when the pen is lifted. We find that the Legendre series representation is just as suitable in practice for the representation and analysis of ink traces as the Chebyshev representation, but has the benefit that it can be computed in a small, fixed number of arithmetic operations at the end of a stroke. Additionally, the fixed number of arithmetic operations at each time step (to compute the moments) and on pen up (to normalize size and compute the series coefficients) makes this technique well suited to use on devices with limited computational capacity.

[presentation slides (PDF 800KB) ]

Computer algebra systems (CASs) may be utilized to edit mathematical expressions by 2-D editors, implemented in any authoring software, such as word processors, e-learning management software, and so on. For example, suppose a monomial basis representation of a polynomial. CASs can compute its factorization form directly on their system. If we can call their function from 2-D editors as well, editing mathematical expressions may be much easier.

For that purpose, full of functionalities of CASs are not necessary. Some sort of CASs that perform a limited function are enough. Supporting interactivity of 2-D editors, efficient implementation is rather important.

The xfy [9] is software for authoring compound XML documents on a workspace. It has extensible architecture with plug-ins or XVCDs. A plug-in is developed in Java through xfy-API. Unlike other useful software for compound XML documents, such as Amaya [1], the xfy has a script language, called XVCD, which is an extension of XSLT to accommodate editing any XML vocabularies easily. Using the xfy's extensible architecture, we hope to develop an authoring environment for any mathematical XML documents on the xfy.

We have already shown some advantages of the xfy on applications for mathematical education [5] and computations using mathematical Web-services [4]. In such applications, it is necessary to handle the syntax of mathematical expressions by MathML content markup [6] or OpenMath [7] easily on the xfy.

Here, we propose yet another MathML content markup editor on the xfy. Our editor is designed as a template editor to edit the syntax of mathematical expressions correctly, like other useful MathML content markup editors, such as Formulator MathML Weaver [2] and Integre MathML Equation Editor [3]. Since our editor is a plug-in component of the xfy, we can provide a seamless authoring environment for compound XML documents including MathML content markup. This is an advantage of our editor.

Further our editor is going to support MathML editing using CAS. For example, here we focus on Maple. Since Maple provides OpenMaple and MathML package, we can easily access Maple algorithms and data structure through Java and XML.

We referred to a helpful paper [8] when we designed the MathML content markup editor with uniform behavior and usability. In order to achieve this goal, we conducted a usability test of our editor versus the other ones, Formulator MathML Weaver and Integre MathML Equation Editor. We examined click count and typing count for ten expressions. The results show our MathML editor works in similar fashion like the other MathML content markup editors.

References
[1] Amaya Home Page, http://www.w3.org/Amaya/.
[2] Formulator MathML Weaver Home Page, http://mmlsoft.com/projects/formulator/.
[3] Integre MathML Equation Editor Home Page, http://www.integretechpub.com/zed/.
[4] Hiroshi Kai, Takayuki Kawata, Tomomi Nakanishi, Matu-Tarow Noda, Yasushi Tamura, Generating A Mathematical Web Service Client With xfy, ACM SIGSAM Bulletin, Vol 41, No 2, pp.38-39, 2007.
[5] Masaki Kume, Atsushi Miyamoto, Hiroshi Kai, Matu-Tarow Noda, and Yasushi Tamura, Mathematical documents authoring on xfy, Mathematical User-Interfaces Workshop 2006 (MathUI), pp.1-8, 2006.
[6] MathML Home Page, http://www.w3.org/TR/MathML2/.
[7] OpenMath Home Page, http://www.openmath.org/.
[8] Luca Padovani and Ricardo Solmi, An Investigation on the Dynamics of Diret-Manipuation Editors for Mathematics, MKM 2004, Lecture Notes in Computer Science, Vol.3119, pp.302-316, 2004.
[9] xfy Home Page, http://www.xfy.com/.

[full paper | presentation slides (PDF 208KB)>]

We present a new Algorithm for In-Place Rectangular Transposition of an m by n matrix A that is efficient. In worst case it is O(N log N) where N = mn. It uses a bit-vector of size IWORK words to further increase its efficiency. When IWORK=0 no extra storage is used. We also review some of the other existing algorithms for this problem. These contributions were made by Gower, Windley, Knuth, Macleod, Laffin and Brebner (ACM Alg. 380), Brenner (ACM Alg. 467), and Cate and Twigg (ACM Alg. 513). Performance results are given and they are compared to an Out-of-Place Transposition algorithm as well as ACM Algorithm 467.

[full paper]