Space-efficient algorithms in computer algebra and image processing applications

点击翻译按钮获取中文摘要

We propose to study problems in a number of areas including computer algebra, image set compression, and mathematical document analysis. Our main focus is on techniques for efficiently reducing the space requirement for both the execution of algorithms and the storage of data. In many important problems in computer algebra, the sizes of the input and the final desired results are relatively small, but intermediate results may grow significantly in many algorithms. Our goal is to develop algorithms that are not only space efficient, but also take memory management in the underlying system into account. We expect that more practical algorithms will be developed as a result. In image set compression, compressing each image individually does not exploit the redundancy that exists between images. We plan to examine techniques to compress a set of images as well as the problem of dynamic updates to image set. We particularly focus on satellite and medical images in which substantial redundancy among images is known to exist. Many mathematical documents are available in digital form only as scanned digital images. We intend to build a system that analyzes these images and store them in a structured form for use by other tools. Of particular interests are recognizing and utilizing abstract concepts in mathematics such as matrix structures (e.g. Toeplitz, Hankel, etc.) and algorithm descriptions. Such a system can be used to build a digital library of mathematical knowledge to be stored efficiently and used by other computer algebra systems.