The 2025 ISSAC conference in Guanajuato, Mexico, marks the 50th event in this significant series, making it an ideal moment to reflect on the field’s history. This paper reviews the formative years of symbolic computation up to 1975, fifty years ago. By revisiting a period unfamiliar to most current participants, this survey aims to shed light on once-pressing issues that are now largely resolved and to highlight how some of today’s challenges were recognized earlier than expected.

The usual formulation of efficient division uses Newton iteration to compute an inverse in a related domain where multiplicative inverses exist. On one hand, Newton iteration allows quotients to be calculated using an efficient multiplication method. On the other hand, working in another domain is not always desirable and can lead to a library structure where arithmetic domains are interdependent. This paper uses the concept of a whole shifted inverse and modified Newton iteration to compute quotients efficiently without leaving the original domain. The iteration is generic to domains having a suitable shift operation, such as integers or polynomials with coefficients that do not necessarily commute.

We present a method to compress digital ink based on piecewise-linear approximation within a given error threshold. The objective is to achieve good compression ratio with very fast execution. The method is especially effective on types of handwriting that have large portions with nearly linear parts, e.g. hand drawn geometric objects. We compare this method with an enhanced version of our earlier functional approximation method, finding the new technique to give slightly worse compression while performing significantly faster. This suggests the presented method can be used in applications where speed of processing is of higher priority than the compression ratio.

Digital ink curves are typically represented as series of points sampled at certain time intervals. We are interested in the problem of how to select a minimal subset of sample points to approximate a digital ink curve within a given error bound. We present an algorithm to find an approximation with a specified number of points and providing the minimum cumulative error. Alternatively, it may be used to select the minimum number of points required to satisfy an error bound. The method uses dynamic programming and has a cost linear in the number of points.

Shape-based online handwriting recognition suffers on small characters, in which the distortions and variations are often commensurate in size with the characters themselves. This problem is emphasized in settings where characters may have widely different sizes and there is no absolute scale. We propose methods that use size information to adjust shape-based classification to take this phenomenon appropriately into account. These methods may be thought of as a pre-classification in a size-based feature space and are general in nature, avoiding hand-tuned heuristics based on particular characters.

We present an adaptive approach to the recognition of handwritten mathematical symbols, in which a recognition weight is associated with each training sample. The weight is computed from the distance to a test character in the space of coefficients of functional approximation of symbols. To determine the average size of the training set to achieve certain classification accuracy, we model the error drop as a function of the number of training samples in a class and compute the average parameters of the model with respect to all classes in the collection. The size is maintained by removing a training sample with the minimal average weight after each addition of a recognized symbol to the repository. Experiments show that the method allows rapid adaptation of a default training dataset to the handwriting of an author with efficient use of the storage space.

We address the problem of handwritten symbol classification in the presence of distortions modeled by affine transformations. We consider shear, rotation, scaling and translation, since these types of transformations occur most often in practice, and focus most on shear within this framework. We present a distance-based classification method, in which feature vectors are constructed from Legendre-Sobolev expansions of the coordinate functions and of the affine integral invariants of the curves given by the symbol's ink strokes. We analyze different size normalization methods and conclude that integral invariants provide the most robust norm. Finally, we propose a new parameterization, a combination of arc length and time, insensitive to variations in curve tracing speed and affine distortion.

We consider the problem of dealing with irrelevant votes when a multi-case classifier is built from an ensemble of binary classifiers. We show how run-off elections can be used to limit the effects of irrelevant votes and the occasional errors of binary classifiers, improving classification accuracy. We consider as a concrete classification problem the recognition of handwritten mathematical characters. A succinct representation of handwritten symbol curves can be obtained by computing truncated Legendre-Sobolev expansions of the coordinate functions. With this representation, symbol classes are well linearly separable in low dimension which yields fast classification algorithms based on linear support vector machines. A set of 280 different symbols was considered, which gave 1635 classes when different variants are labelled separately. With this number of classes, however, the effect of irrelevant classifiers becomes significant, often causing the correct class to be ranked lower. We introduce a general technique to correct this effect by replacing the conventional majority voting scheme with a runoff election scheme. We have found that such runoff elections further cut the top-1 mis-classification rate by about half.

Representing digital ink traces as points in a function space has proven useful for online recognition. Ink trace coordinates or their integral invariants are written as parametric functions and approximated by truncated orthogonal series. This representation captures the shape of the ink traces with a small number of coefficients in a form quite compact and independent of device resolution, and various geometric techniques may be employed for recognition. The simplicity and high performance of this method lead us to ask whether the same idea can be applied to another important aspect in online handwriting the compression of digital ink strokes. We have investigated Chebyshev, Legendre and Legendre-Sobolev orthogonal polynomial bases as well as Fourier series and have found that Chebyshev representation is the most suitable apparatus for compressing digital curves. We obtain compression rates of 30× to 50× and have the added benefit that the Legendre-Sobolev form, used for recognition, may be obtained by a single linear transformation.

We propose an efficient method to recognize multi-stroke handwritten symbols. The method is based on computing the truncated Legendre-Sobolev expansions of the coordinate functions of the stroke curves and classifying them using linear support vector machines. Earlier work has demonstrated the efficiency and robustness of this approach in the case of single-stroke characters. Here we show that the method can be successfully applied to multi-stroke characters by joining the strokes and including the number of strokes in the feature vector or in the class labels. Our experiments yield an error rate of 11-20%, and in 99% of cases the correct class is among the top 4. The recognition process causes virtually no delay, because computation of Legendre-Sobolev expansions and SVM classification proceed on-line, as the strokes are written.

With the increased availability of pen-based devices, it becomes interesting to conduct and to archive multi-party communication sessions that involve audio and digital ink on a shared canvas. Collaborative whiteboards do exist today but typically use complex or closed protocols for communication. As a rule, existing whiteboards are not interoperable across multiple platforms and do not support archival of collaborative sessions for later reference or analysis. We explore how various data formats may be used to represent, to transmit, to record and to synchronize ink and audio channels. We find InkML to be a suitable representation to support platform-independent digital ink in a form supporting both transmission and higher-level semantic analysis. To test our ideas we have developed a complete software implementation as a Skype add-on. This has revealed possible improvements to the page and streaming models of InkML.

Classes of matrices are often presented with symbolic dimensions using a mixture of terms and ellipsis symbols to describe their internal structure. While working with such classes of matrices is everyday mathematical practice, it has little automated support. We describe an algebraic encoding of such matrices in terms of support functions and define the corresponding addition and multiplication algorithms. It is, however, non-trivial to retrieve the structural description of the matrix resulting from these operations. We therefore define an abstract matrix as an encoding of support function combinations that enables simple recovery of the structural properties. This allows us to define arithmetic algorithms for abstract matrices as extensions of those for support function combinations using a normalising term rewrite system.

Tracing algorithms visit reachable nodes in a graph and are central to activities such as garbage collection, marshalling etc. Traditional sequential algorithms use a worklist, replacing a nodes with their unvisited children. Previous work on parallel tracing is processor-oriented in associating one worklist per processor: worklist inser-tion and removal requires no locking, and load balancing requires only occasional locking. However, since multiple queues may con-tain the same node, significant locking is necessary to avoid con-current visits by competing processors. This paper presents a memory-oriented solution: memory is par-titioned into segments and each segment has its own worklist con-taining only nodes in that segment. At a given time at most one pro-cessor owns a given worklist. By arranging separate single-reader-single-writer forwarding queues to pass nodes from processor i to processor j we can process objects in an order that gives lock-free mainline code and improved locality of reference. This refactoring is analogous to the way in which a compiler changes an iteration space to eliminate data dependencies. While it is clear that our solution can be more effective on NUMA systems, and even necessary when processor-local memory may not be addressed from other processors, slightly surprisingly, it often gives significantly better speed-up on modern multi-cores architectures too. Using caches to hide memory latency loses much of its effectiveness when there is significant cross-processor mem-ory contention or when locking is necessary.

Certain forms of mathematical expression are used more often than others in practice. A quantitative understanding of actual usage can provide additional information to improve the accuracy of software for the input of mathematical expressions from scanned documents or handwriting and more natural forms of presentation of mathematical expressions by computer algebra systems. Earlier work has examined this question for the diverse set of articles from the mathematics preprint archive arXiv.org. That analysis showed showed the variance between mathematical areas. The present work analyzes a particular mathematical domain more deeply. We have chosen to examine second year university engineering mathematics as taught in North America as the domain. We have analyzed the set of expressions occurring in the most popular textbooks, weighted by popularity. Assuming that early training influences later mathematical usage, we take this as a model of the set of mathematical expressions used by the population of North American engineers. We present an empirical analysis of the symbols and $n$-grams occurring in these expressions.

We model on-line ink traces for a set of 219 symbols to "best fit" low-degree polynomial series. Using a collection of mathematical writing samples, we find that in many cases this provides a succinct way to model the stylus movements of actual test users. Furthermore, even without further similarity-processing, the polynomial coefficients from the writing samples form clusters which often contain the same character as written by different users. We find this style of characterization to be an attractive tool due to the suitability of the representation to computation and mathematical analysis.

Recognition of mathematical symbols is a challenging task, with a large set with many similar symbols. We present a support vector machine based hybrid recognition system that uses both online and offline information for classification. Probabilistic outputs from the two support vector machine based multi-class classifiers running in parallel are combined by taking a weighted sum. Results from the experiments show that giving slightly higher weight to the on-line information produces better results. The overall error rate of the hybrid system is lower than that of both the online and offline recognition systems when used in isolation.

Ink markup language (InkML) provides a platform-neutral data format that can be used to represent, store and transmit digital ink data. Both streaming and archival applications are supported through different uses of InkML's primitives. While streaming ink and archival ink data can represent the same information, each supports certain operations more directly. Indeed, certain applications can benefit from access to both representations of the same digital ink data. In this paper we present an efficient method to convert archival style InkML to streaming style and vice-versa.

We address the question of recognizing handwritten mathematics in Arabic and related languages. After presenting an overview of the major styles used to express mathematics in these settings we outline potential problems specific to the representations. Finally, we discuss how some existing strategies for on-line analysis of handwritten mathematics can be adapted for this context.

As pen-based computing becomes more prevalent, it is increasingly important to be able to share ink across applications and across platforms. The emerging standard Ink Markup Language (InkML) is intended for this purpose. Four drafts of the proposed standard have been produced since 2003, resulting in a specification with broad input from industry and invited experts. The last working draft has simplified and generalized the specification in some important ways and the specification is now in "last call" status. This paper presents an overview of the main features of InkML, with an emphasis on the rationale for what has changed for the last call version.

Natural and convenient mathematical handwriting recognition requires recognizers for large sets of handwritten symbols. This paper presents a recognition system for such handwritten mathematical symbols. We use a pre-classification strategy, in combination with elastic matching, to improve recognition speed. Elastic matching is a model-based method that involves computation proportional to the set of candidate models. To solve this problem, we prune prototypes by examining character features. To this end, we have defined and analyzed different features. By applying these features into an elastic recognition system, the recognition speed is improved while maintaining high recognition accuracy.

This paper describes a method to use compiled, strongly typed Aldor domains in the interpreted, expression-oriented Maple environment. This represents a non-traditional approach to structuring computer algebra software: using an efficient, compiled language, designed for writing large complex mathematical libraries, together with a top-level system based on user-interface priorities and ease of scripting.We examine what is required to use Aldor libraries to extend Maple in an effective and natural way. Since the computational models of Maple and Aldor differ significantly, new run-time code must implement a non-trivial semantic correspondence. Our solution allows Aldor functions to run tightly coupled to the Maple environment, able to directly and efficiently manipulate Maple data objects. We call the overall system Alma.

Parametric polymorphism has become a common feature of mainstream programming languages, but software component architectures have lagged behind and do not support it. We examine the problem of providing parametric polymorphism with components combined from different programming languages. We have investigated how to resolve different binding times and parametrization semantics in a range of representative languages and have identified a common ground that can be suitably mapped to different language bindings. We present a generic component architecture extension that provides support for parameterized components and that can be easily adapted to work on top of various software component architectures in use today (e.g., corba, dcom, jni). We have implemented and tested this architecture on top of corba. We also present Generic Interface Definition Language (gidl), an extension to corba-idl supporting generic types and we describe language bindings for C++, Java and Aldor. We explain our implementation of gidl, consisting of a gidl to idl compiler and tools for generating linkage code under the language bindings. We demonstrate how this architecture can be used to access C++'s stl and Aldor's BasicMath libraries in a multi-language environment and discuss our mappings in the context of automatic library interface generation.

In this paper, we propose a new semi-numerical algorithmic method for factoring multivariate polynomials absolutely. It is based on algebraic and geometric properties after reduction to the bivariate case in a generic system of coordinates. The method combines 4 tools: zero-sum relations at triplets of points, partial information on monodromy action, Newton interpolation on a structured grid, and a homotopy method. The algorithm relies on a probabilistic approach and uses numerical computations to propose a candidate factorization (with probability almost one) which is later validated.

A new algorithm is presented for factoring bivariate approximate polynomials over C[x, y]. Given a particular polynomial, the method constructs a nearby composite polynomial, if one exists, and its irreducible factors. Subject to a conjecture, the time to produce the factors is polynomial in the degree of the problem. This method has been implemented in Maple, and has been demonstrated to be efficient and numerically robust.

The (4 0,) (1:) or fadoretl fornl.For exau~ple~ a. demise polynomial of degree IL woultl take approsimately 2r1 operat.ionst.o cva1uat.e in eitlwr espandcd or factin form.-4 presentatiori itS two cornlx~sit.ionfac:tor.r;,however: ~voldtl t,akr l>etw:rn 4&i and II aritlm&ic operations.main results of this pilpcr illC ail iterative nictliod t,o conlput~e il.decomposit.ion of a giveu itpprosillla~.e pOl~IlOIlliill, giveIl a starting point.

The first official version of the OpenMath specification was released in December. This paper presents the first implementation of this standard, in the form of a C library. To ensure a faithful realization, a second, independent implementation with the same API was built using Alder (A ”). We describe how the C library has been embedded in two main-stream computer algebra systems, Maple and Reduce, which can now communicate with each other and Alder, and with specialized programs also linking the libraries. We discuss some of the problems encountered in developing the.4P1.and the solutions we have chosen. 1

Article Free Access Share on A numerical absolute primality test for bivariate polynomials Authors: André Galligo Laboratoire de Mathématiques, Université de Nice, France Laboratoire de Mathématiques, Université de Nice, FranceView Profile , Stephen Watt IBM T.J. Watson Research Center and INRIA Sophia Antipolis, France IBM T.J. Watson Research Center and INRIA Sophia Antipolis, FranceView Profile Authors Info & Claims ISSAC '97: Proceedings of the 1997 international symposium on Symbolic and algebraic computationJuly 1997 Pages 217–224https://doi.org/10.1145/258726.258788Published:01 July 1997Publication History 22citation207DownloadsMetricsTotal Citations22Total Downloads207Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Dynamic evaluation is a technique for producing multiple results according to a decision tree which evolves with program execution. Sometimes it is desired to produce results for all possible branches in the decision tree, while on other occasions it may be sufficient to compute a single result which satisfies certain properties. This technique finds use in computer algebra where computing the correct result depends on recognising and properly handling special cases of parameters. In previous work, programs using dynamic evaluation have explored all branches of decision trees by repeating the computations prior to decision points. This paper presents two new implementations of dynamic evaluation which avoid recomputing intermediate results. The first approach uses Scheme "continuations" to record state for resuming program execution. The second implementation uses the Unix "fork" operation to form new processes to explore alternative branches in parallel. These implementations are based on ...

This paper introduces singular value decomposition (SVD) algorithms for some standard polynomial computations, in the case where the coefficients are inexact or imperfectly known. We first give an algorithm for computing univariate GCD's which gives exact results for interesting nearby problems, and give efficient algorithms for computing precisely how nearby. We generalize this to multivariate GCD computation. Next, we adapt Lazard's u-resultant algorithm for the solution of overdetermined systems of polynomial equations to the inexact-coefficient case. We also briefly discuss an application of the modied Lazard's method to the location of singular points on approximately known projections of algebraic curves.

Article Free Access Share on A first report on the A# compiler Authors: Stephen M. Watt IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NY IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NYView Profile , Peter A. Broadbery IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NY IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NYView Profile , Samuel S. Dooley IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NY IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NYView Profile , Pietro Iglio IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NY IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NYView Profile , Scott C. Morrison Autodesk, Multimedia Division, 2320 Marinship Way, Sausalito, CA and IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NY Autodesk, Multimedia Division, 2320 Marinship Way, Sausalito, CA and IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NYView Profile , Jonathan M. Steinbach IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NY IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NYView Profile , Robert S. Sutor IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NY IBM Thomas J. Watson Research Center, P.O. BOX 218, Yorktown Heights, NYView Profile Authors Info & Claims ISSAC '94: Proceedings of the international symposium on Symbolic and algebraic computationAugust 1994 Pages 25–31https://doi.org/10.1145/190347.190356Online:01 August 1994Publication History 16citation283DownloadsMetricsTotal Citations16Total Downloads283Last 12 Months15Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF