Algebraic & Numerical Computation
Rationale
Algebraic and Numerical Algorithms, and in particular matrix and polynomial algorithms, are the backbone of the modern computations in Sciences, Engineering, and Signal and Image Processing. For example, they are routinely invoked when we turn on our computers, TVs or radios. Due to the demand, the subject has been enjoying high respect in the fields of Computer Science and Computational Mathematics. It is also the source of exciting research challenges in these relatively new dynamic fields. The course will introduce the students to some most fundamental methods and techniques of symbolic and numerical computations. It will provide insights into these fields and some experience in the design, analysis and implementation of modern algorithms and can lead students to research, currently supported by the Instructor’s NSF Grant, to publications in Journals and Proceedings of Conferences, and to the defenses of PhD Theses.
Description
The course will cover some fundamental topics in both symbolic and numerical computations. The area of this study is large. THE INSTRUCTOR CAN ADJUST THE TOPICS TO STUDENTS’ INTERESTS, AND ACCORDINGLY, HE CAN NARROW OR EXTEND THE LIST OF TOPICS BELOW. He will facilitate the students’ study by supplying reading materials selectively and by exploiting the link between the computations with structured matrices and polynomials, which he has covered in some detail in his two books and many research and survey papers. In his previous teaching experience in the Graduate Center this guiding link enabled deep advance into the central subjects of the fields of study, even for the students having no previous knowledge and experience. The course will bring them to the research frontiers in both areas of Computer Science and Computational Mathematics, and can lead them to PhD defenses (so far the Instructor has guided 10 successful PhD defenses in each of the CUNY Programs in Computer Science and Mathematics). The students coming from both areas will be able to participate (under the instructors’ NSF grant) in the advanced study of recent and new algorithms, in their formal mathematical analysis and computer implementation. The instructor will encourage joint study and research of the students from Computer Science and Mathematics to the benefits of both groups. (In 2013 he has been designated a Fellow of the American Math. Society for his “Contributions to the Mathematical Theory of Computation.) He will be happy to arrange additional meetings with the advanced students to guide them towards their research publications and PhD degree and would supply materials for this study, but the students can obtain 3 credits just for successful learning.
Topic List

Basic operations of computer algebra (polynomials and rational multiplication, division, multipoint evaluation, interpolation, computing GCDs and LCMs)

Structured matrices such as Toeplitz, Hankel, factor circulant, Vandermonde, Cauchy, Frobenius, Resultant, and HSS matrices

Efficient algorithms for structured matrices. Their link to computations with polynomials and rational functions

Data compression by using matrix structures

General matrices, their factorizations, norms and other basic concepts and techniques of matrix computations

Techniques for error control and estimation in numerical computing with rounding

Parallel matrix and polynomial algorithms
Leaning Goals
Students are expected to

Understand the basic principles, concepts and techniques of symbolic and numerical computing

Learn some fundamentals of algorithm design and analysis

Learn efficient algorithms for most popular operations with polynomials, rational functions and general and structured matrices

Learn the basic techniques of data compression for structured matrices

Learn and possibly practice the basics of the implementation of symbolic and numerical algorithms

Get a chance to advance in research, publications and preparation to PhD defense based on their study of Algebraic and Numerical Algorithms
Assessment

Class participations and discussions will be used to evaluate students' understanding of concepts of algebraic and numerical computations. The attendance and participation account for 10% of the final grade

Homework assignments (40% of the final grade) will be designed to provide the opportunities for students to verify their understanding of the current subjects of the study and their ability to employ the relevant techniques and algorithms introduced for Algebraic and Numerical Computing

Final and possibly midterm tests will represent 50% of the final grade. They will give students chances to show their overall understanding of the course subjects

The students’ advances in research and implementation of recent and new algorithms can demonstrate their knowledge and understanding of the course materials. This will be counted as partial substitution for the homework and exams towards the final grade