Show The Graduate Center Menu

Algebraic & Numerical Computation

 
 

Algebraic & Numerical Computation

Instructor: Distinguished Professor Victor Pan

  • Tuesdays, 4.15 – 6.15; also 6.30 - 8:30 pm
     

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

  • Fast Fourier transform
  • 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
  • Randomization methods


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