Space-efficient algorithms in computer algebra and image processing applications

我们建议研究一些领域的问题，包括计算机代数、图像集压缩和数学文档分析。我们主要关注的是有效减少算法执行和数据存储的空间需求的技术。在计算机代数的许多重要问题中，输入和最终期望结果的大小相对较小，但在许多算法中，中间结果可能会显着增长。我们的目标是开发不仅具有空间效率的算法，而且还考虑到底层系统中的内存管理。我们期望由此开发出更实用的算法。在图像集压缩中，单独压缩每个图像不会利用图像之间存在的冗余。我们计划研究压缩一组图像的技术以及图像集的动态更新问题。我们特别关注卫星和医学图像，其中图像之间存在大量冗余。许多数学文档只能以扫描数字图像的形式以数字形式提供。我们打算建立一个系统来分析这些图像，并以结构化的形式存储它们，以供其他工具使用。特别感兴趣的是识别和利用数学中的抽象概念，如矩阵结构（如Toeplitz， Hankel等）和算法描述。这样的系统可以用来建立一个数字图书馆的数学知识，有效地存储和其他计算机代数系统使用。

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.