Revised 05/95 SELECTED 500-LEVEL COURSE DESCRIPTIONS DEPARTMENT OF MATHEMATICS COLORADO STATE UNIVERSITY M501-M502 Introduction to Combinatorial Theory Credits: M501 3 (3-0-0); M502 3 (3-0-0) Term Offered: M501 - Fall; M501 - Spring Prerequisite: M301, M369 or equivalent Text: Introductory Combinatorics by R.A. Brualdi, supplemented by material from Graph Theory, A Development from the 4-Color Problem by M. Aigner (graphs), and Combinatorial Designs by Ian Anderson. Description: Combinatorial theory is widely regarded as a delightful branch of mathematics. It contains some of the cleverest proofs in all of abstract reasoning, and has a broad range of applications. As the mathematical basis of theoretical computer science, combinatorial theory has enjoyed a huge surge of interest and popularity over the last 25 years, and is a very active research area. Our one-year sequence in combinatorial theory divides into three parts: counting, graphs, and algebraic combinatorics. The counting segment of the course includes elementary counting, binomial identities, generating functions, recurrence relations, counting numbers (Stirling, Catalan), Ramsey theory, inclusion- exclusion, mobius inversion, and Polya counting. The section on graph theory covers basic concepts, connectivity, planarity, colorings, bipartite and non-bipartite matchings, transversals, network flows, Latin squares, factors, hamiltonian cycles, and extremal graph theory. These are the central ideas of graph theory, and incidently include all the necessary tools for understanding the 1976 proof (by Appel and Haken) of the famous 4-color theorem. The section on algebraic combinatorics introduces some structures that are both combinatorial and algebraic. These include balanced incomplete block designs used in statistics, linear codes used in communications, and Hadamard matrices and finite geometries used in weighing schemes, design of tournaments, and certain security schemes. EG/M510 Linear Programming and Networks Credits: 3 (3-0-0) Term Offered: Spring Prerequisite: M261 or M315 Text: R. B. Darst, Introduction to Linear Programming: Applications and Extensions, Marcel-Dekker, 1991 Topics: 1. Examples of problems to which LP applies: production, diet, and transportation problems. 2. Duality. 3. Properties of the feasible set for an LP; basic feasible solutions. 4. An introduction to the simplex method 4.1 Notation 4.2 Pertinent Algebra 4.3 The Simplex Tableau 4.4 Reduced Costs 4.5 Conditions for Optimality 4.6 The Objective Function 4.7 Simplex Method Pivoting 4.8 When No Optimal Solution Exists 4.9 Multiple Solutions 4.10 Degeneracy 4.11 Phase One 4.12 The Revised Simplex Method 4.13 Stability and Sensitivity 5. Multiperiod Problems 6. Integer Variables 7. Transportation Problems 8. Networks 9. Out of Kilter Formulation 10. Kuhn-Tucker Conditions 11. Primal-Dual Method 12. Quadratic Programming 13. Dynamic Programming 14. Network Algorithms 14.1 Longest Path Algorithm 14.2 Shortest Path Algorithm 14.3 Minimal Spanning Tree Algorithm 14.4 Max (Simple) Path Flow Algorithm 14.5 Residual Digraph 14.6 Max Flow Algorithm 14.7 Min Cost Flows: Transportation and Assignment Problems 14.8 Min Cost Max Flow Algorithm GS510 Fundamentals of High Performance Computing Credits: 3 (2-1-0) Term Offered: Fall Description: Graduate students just beginning a computational research project and researchers who have been away from the area of high performance computing for more than a year can benefit from the course GS-510. In this course, we aim to provide students with the tools necessary to work effectively in a highly networked computing environment involving machines ranging from work- stations to CRAYs. The course assumes that students are familiar with either FORTRAN or C. The course provides students with an overview of UNIX, basic networking skills, an introduction to vector and parallel architectures and an introduction to scientific visualization. The course GS-510 carries 3 (2-1) credits with two classes per week and a computer laboratory. Topics: UNIX Basics A Primer on vi (the "universal" editor) Shells and Shell Programming Telnet and ftp UNICOS and the CFT compiler IRJE and NQS Principles of Vectorization Principles of Parrallelization Amdhal's Law Vectorization/Parallelization Techniques Vectorization/Parallelization Inhibitors Timing Tests Scalar vs Vector vs Parallel Visualization Instructor: Cooley/Zachmann GS511 High Performance Computing and Visualization Credits: 3 (2-1-0) Term Offere: Spring Description: The term Computational Scientist has been coined to describe scientists, engineers and mathematicians who apply high- performance computational technology in an innovative and essential way to advance the state of knowledge in their discipline. In the areas of high performance computing and numerical modeling, the effective computational scientist needs to have command of an applied discipline and must be familiar with leading edge computer architectures and algorithms. Also, visualization techniques for the pre and post processing of model data are becoming an essential tool in the area of computational science. Goal: The goal of the course GS-511 is to enable students to develop skills required of an effective computational scientist. Since the solution of systems of linear equations is central to much of computational science, the GS-511 course spends a good deal of time discussing efficient data structures and solution methods for this important class of problems. Special attention is given to sparse, banded systems of equations, such as those arising in connection with the finite difference and finite element methods. The course highlights the interplay between storage considerations, algorithm convergence rate and CPU performance. The matching of an algorithm and an architecture are given considerable attention. The course focuses on the CRAY YMP architecture, but students also compute on a Connection and a variety of workstations. Introductory material on visualization and image processing is presented. GS-511 is a 3 (2-1) credit course meeting twice per week with a credit of computer laboratory. Topics: Systems of Linear Equations Arising in Computational Science Iterative vs Direct Methods Jacobi, Gauss-Seidel and SOR: Convergence and Vectorization Conjugate Gradient Method Implementation of CG Method to Sparse, Banded Systems of Equations Preconditioners for CG Method Performance comparisons of Jacobi, GS, SOR, Red-Black ADI and CG Library Routines and Software Packages Monte Carlo Methods Visualization and Image Processing Instructor: D. Zachmann M517 Introduction to Mathematical Analysis I Credits: 3 (3-0-0) Term Offered: Fall Prerequisite: M318 Text: W. Rudin, Principles of Mathematical Analysis, 3rd ed, McGraw-Hill, New York, 1976 Topics: - Finite, countable, and uncountable sets. - Real and complex number systems, and Euclidean k-space. - Metric spaces: open and closed sets, compact and connected sets, convergent sequences, Cauchy sequences, completeness, continuous functions, continuity and compactness, and continuity and connectedness. - Numerical sequences and series: tests for convergence, power series, absolute convergence, conditional convergence, and rearrangements. - Differentiation theory: the derivative, mean value theorems, l'Hospital's rule, Taylor's theorem, and differentiation of vector-valued functions. - Integration theory: the Riemann-Stieltjes integral, basic properties, fundamental theorem of calculus, and rectifiable curves. - Sequences and series of functions: uniform convergence, uniform convergence and continuity, uniform convergence and integration, uniform convergence and differentiation, Weierstrass approximation theorem, and Stone-Weierstrass theorem. GS511 High Performance Computing and Visualization Credits: 3 (2-1-0) Term Offere: Spring Description: The term Computational Scientist has been coined to describe scientists, engineers and mathematicians who apply high- performance computational technology in an innovative and essential way to advance the state of knowledge in their discipline. In the areas of high performance computing and numerical modeling, the effective computational scientist needs to have command of an applied discipline and must be familiar with leading edge computer architectures and algorithms. Also, visualization techniques for the pre and post processing of model data are becoming an essential tool in the area of computational science. Goal: The goal of the course GS-511 is to enable students to develop skills required of an effective computational scientist. Since the solution of systems of linear equations is central to much of computational science, the GS-511 course spends a good deal of time discussing efficient data structures and solution methods for this important class of problems. Special attention is given to sparse, banded systems of equations, such as those arising in connection with the finite difference and finite element methods. The course highlights the interplay between storage considerations, algorithm convergence rate and CPU performance. The matching of an algorithm and an architecture are given considerable attention. The course focuses on the CRAY YMP architecture, but students also compute on a Connection and a variety of workstations. Introductory material on visualization and image processing is presented. GS-511 is a 3 (2-1) credit course meeting twice per week with a credit of computer laboratory. Topics: Systems of Linear Equations Arising in Computational Science Iterative vs Direct Methods Jacobi, Gauss-Seidel and SOR: Convergence and Vectorization Conjugate Gradient Method Implementation of CG Method to Sparse, Banded Systems of Equations Preconditioners for CG Method Performance comparisons of Jacobi, GS, SOR, Red-Black ADI and CG Library Routines and Software Packages Monte Carlo Methods Visualization and Image Processing Instructor: D. Zachmann M517 Introduction to Mathematical Analysis I Credits: 3 (3-0-0) Term Offered: Fall Prerequisite: M318 Text: W. Rudin, Principles of Mathematical Analysis, 3rd ed, McGraw-Hill, New York, 1976 Topics: - Finite, countable, and uncountable sets. - Real and complex number systems, and Euclidean k-space. - Metric spaces: open and closed sets, compact and connected sets, convergent sequences, Cauchy sequences, completeness, continuous functions, continuity and compactness, and continuity and connectedness. - Numerical sequences and series: tests for convergence, power series, absolute convergence, conditional convergence,and rearrangements. - Differentiation theory: the derivative, mean value theorems, l'Hospital's rule, Taylor's theorem, and differentiation of vector-valued functions. - Integration theory: the Riemann-Stieltjes integral, basic properties, fundamental theorem of calculus, and rectifiable curves. - Sequences and series of functions: uniform convergence, uniform convergence and continuity, uniform convergence and integration, uniform convergence and differentiation, Weierstrass approximation theorem, and Stone-Weierstrass theorem. M518 Introduction to Mathematical Analysis II Credits: 3 (3-0-0) Term Offered: Spring Prerequisite: M369, M517 Topics: Differentiation of functions of several variables: norms of linear transformations, the derivative, chain rule, mean value theorems, equality of mixed partials, higher derivatives, Taylor's theorem, and second derivative test for max-min. Inverse and implicit function theorems. Multiple integrals: the integral, basic properties, Darboux's theorem, sets of measure zero and content zero, Lebesgue's theorem, sets having volume, and Fubini's theorem. Change of variables for multiple integrals. Green's theorem, Stokes' theorem, and the divergence theorem. M519 Complex Analysis Credits: 3 (3-0-0) Term Offered: Fall Prerequisite: M317 Topics: The Complex Number System Power Series Analytic Functions Exponential Function Trigonometric Functions Branches of the Logarithm Cauchy-Riemann Equations Cauchy's Integral Formula Power Series Representation of Analytic Functions Zeroes of an Analytic Function Liouville's Theorem Fundamental Theorem of Algebra Index of a Closed Curve Open Mapping Principle Singularities Laurent Series Residue Theorem Argument Principle Maximum Modulus Theorem M531 Applied Mathematics I Credits: 3 (3-0-0) Term Offered: Fall, Spring Prerequisite: M340 Text: Linear Algebra and differential Equations, Alan Jeffrey-Blackwell Scientific 1991 Description: Theory and applications of systems of linear algebraic equations; the algebraic eigenvalue problem. Theory and applications of single ordinary differential equations. Systems of linear and nonlinear ordinary differential equations. Laplace transform techniques for differential equations. The emphasis in this course is on the applications, particularly deriving, solving and interpreting discrete and semidiscrete mathematical models for physical systems. M532 Applied Mathematics II Credits: 3 (3-0-0) Term Offered: Fall, Spring Prerequsite: M340 Text: Applied Partial Differential Equations by DuChateau and Zachmann Chapters 1 through 5 Topics: This is an introductory course in solution methods for boundary value and initial boundary value problems in partial differential equations. The emphasis is on the physical motivation and interpretation of solutions rather than on mathematical technicality. The course follows the following outline: mathematical modeling of physical systems Fourier series and eigenfunction expansions separation of variables on bounded domains-eigenfunction expansions integral transforms of Fourier and Laplace separation of variables on unbounded domains-integral transforms M540 Dynamical Systems Credits: 3 (3-0-0) Term Offered: Fall Prerequisites: M318; M369 or consent of instructor Description: This course deals with the qualitative analysis of nonlinear dynamical systems, a central topic in applied mathematics. The geometrical techniques we consider originated with the work of Henri PoincarŽ in his study the stability of the solar system and emphasize the use of a phase portrait and the characterization of a dynamical system as a field of vectors in phase space. This view permits an elegant description of the long term behavior of a system and provides information that a direct numerical simulation cannot. In addition, we discuss the bifurcation of solutions of dynamical systems, i.e., radical changes in the geometry of phase space as we perturb the coefficients of the equations. This course is recommended for students who have had under- graduate courses in ordinary differential equations and linear algebra. It forms the basis for more advanced study in dynamical systems theory and related areas such as modeling, control theory and fluid dynamics. Content: We will begin with a review of the linear theory of ODEs from a geometrical viewpoint followed by iterated maps, asymptotic behavior, local bifurcations, topological equivalence, structural stability, center manifold theory, normal forms, unfoldings and higher codimension bifurcations, chaotic dynamical systems and strange attractors. The course will be taught from a qualitative perspective, no computer coding will be required. M545 Partial Differential Equations Credits: 3 (3-0-0) Term Offered: Fall Prerequisite: M340 Description: An introductory course in PDE covering: origins of PDE classification of PDE; existence, uniqueness and continuous dependence of solutions to initial and boundary value problems; maximum/minimum principles; energy integrals; characteristics; Fourier methods solution techniques constitute approximately 40% of the course with the remaining 60% emphasizing qualitative analysis of PDE problems. Topics: Mathematical Models & Origins of PDE Integral Cons. Laws ® PDE Cons. Laws Laplace Equation Diffusion Equation Second Order Wave Equation First Order Wave Equation Auxiliary Conditions; Well Posedeness Classification and Characteristics (2) Dimensional Analysis and Similarity Solutions (20 Linearity and superposition Applications of Superposition (2) Product Law and DuHumel's Principle Fourier Series (4) Separation of Variables Diffusion Equation Laplace Equation Second Order Wave Equation Harmonic => Mean Value Property Mean Value Property => Maximum Principle Harmonic <=> Mean Value Property Subharmonic and Superharmonic Extended Maximum Principles (2) Uniqueness Results -- Laplace Equation Dirichlet; Neumann; Exterior A Priori Extimates -- Laplace Equation Maximum Principle for Diffusion Equation Uniqueness Results -- Diffusion Equation Dirichlet; Neumann; Exterior A Priori Estimates -- Diffusion Equation D'Alembert Solution -- Second Order Wave Eq. Uniqueness Results -- Second Order Wave Eq. (About 38 days to cover these topics. Remainder for testing and discussion.) M546 Partial Differential Equations II Credits: 3 (3-0-0) Term Offered: Spring Description: This course focuses mainly on analytical techniques for solving and analyzing partial differential equations. Topics: Systems of First Order Equations characteristics shocks generalized solutions Introduction to the Theory of Distributions Dirac delta function calculus of distributions Green's Functions method of images eigenfunction expansions Variational Methods energy integrals Rayleigh Ritz method Galerkin's method Integral Transforms Fourier transform Laplace transform M550 Difference Methods for Solving Partial Differential Equations Credits: 3 (3-0-0) Term Offered: Spring Description: This course focuses mainly on finite difference methods for approximating the solution of partial differential equations. Students entering this class should be comfortable with a scientific programming language such as FORTRAN or C. Topics: Difference methods for parabolic equations discretization errors, convergence and convergence and consistency implicit and implicit difference methods stability algorithm development Solution methods for hyperbolic equations first order equations implicit and explicit defference methods stability and the CFL condition dispersion and dissipation numerical method of characteristics numerical boundary conditions second order equations algorithm development Difference methods for elliptic equations direct and inerative solution methods convergence rates of the Jacobi, Gauss-Seidel, SOR and Conjugate Gradient methods discrete Fourier transforms M560 Linear Algebra Credits: 4 (4-0-0) Term Offered: Fall Topics: 1. Vector Spaces scalar field span subspace linear dependence and independence basis and dimension extension to a basis direct sum decompositions 2. Linear Transformations matrix operators range nullspace rank singularity and nonsingularity linear functionals representations 3. Linear Equations fields systems of linear equations matrices and elementary row operations row-reduced echelon matrices matric multiplication invertible matrices 4. Inner Products and Norms inner products orthogonality norms adjoints (and transposes) symmetry and self-adjointness positive definiteness positive definite symmetric Gram-Schmidt process matrix norms 5. Invariant Subspaces eigenvalues and eigenvectors geometric and algebraic multiplicities characteristic polynomials eigenstructure of symmetric matrices eigenfunction expansions generalized eigenvectors Jordan form singular value decompsoition M561 Numerical Analysis I Credits: 4 (4-0-0) Term Offered: Spring Prerequisites: M369 and preparedness to do programming in a standard language Text: There are many possible texts. One of them is: Stoer J. and Bulirsch, R., Introduction to Numerical Analysis, 1980, Springer. Course Objective: To provide our graduate students with a broad overview on basic topics in Numerical Analysis. Problem solving is emphasized. Course Content: 1. Factorization Methods for Matrices (a) Gauss Elimination and LU Factorization (b) Cholesky Factorization (c) QR Factorization (d) Underdetermined and Overdetermined Systems 2. Iterative Methods for Linear Equations (a) Jacobi and Gauss-Seidel (b) SOR (c) Conjugate Gradient Methods 3. Eigenvalue Problems (a) Singular Value Decomposition (b) Power Method, Inverse Iteration (c) QR Algorithm (d) Jacobi Method (e) Lanczos Methods 4. Nonlinear Equations (a) Bisection (b) Fixed Point Iteration (c) Aitken Extrapolation (d) Newton-like Methods (e) Least Squares (f) Unconstrained Optimization (g) Linear Programming Format: Traditional math. class -- lectures, problem solving, discussion Methods of Evaluation: Written homework, hour exams, and final exam M651 Numerical Analysis II Credits: 4 (4-0-0) Term Offered: Fall Prerequisites: M369 and preparedness to do programming in a standard language Text: Thre are many possible possible texts. One of them is: Stoer, J. and Bulirsch, R., Introdtuion to Numerical Analysis, 1980, Springer. Course Objective: To provide our graduate students with a broad overview on basic topics in Numerial Analysis. Problem solving is emphasized. Course Content: 1. Interpolation (a) Polynomial Interpolation (b) Divided Differences (c) Hermite Interpolation (d) Cubic Splines (e) Trigonometric Interpolation (f) Fast Fourier Transform 2. Approximation (a) Minimax Problems (b) Least Squares Problems 3. Quadrature (a) Integration by Interpolation (b) Adaptive Integration (c) Gau§ Quadrature (d) Integration by Extrapolation 4. Initial Value Problems (a) Runge-Kutta Methods (b) Predictor-Corrector Methods (c) Extrapolation based on the Midpoint Rule (d) Stability and Convergence (e) Stiffness 5. Boundary Value Problems (a) Shooting Method (b) Finite Difference Methods (c) Finite Element Methods Format: Traditional math. class -- lectures, problem solving, discussion Method of Evaluation: Written homework, hour exams, and final exam M566 Introduction to Abstract Algebra I Credit: 3 (3-0-0) Term Offered: Fall Text: Algebra by M. Artin Topics: - Matrix Operations: row reduction, determinants, permutation matrices, Cramer's rule - Groups: basic definitions, subgroups, isomorphisms, homo- morphisms, equivalence relations and partitions, cosets, products, modular arithemtic, quotient groups - Vector Spaces: Abstract fields, bases, dimension, computation with bases, infinite-dimensional spaces, direct sums - Linear Transformations: dimension formula, matrices, linear operators and eigenvectors, characteristic polynomials, orthogonal matrices and rotations, diagonalization - Symmetry: plane figures, motions of the plane, finite and discrete groups of motions, abstract group actions, coset actions, the counting formula, permutation representations, finite subgroups of SO (3). - More Group Theory: group actions of the group, class equations, the Sylow theorems, classification of groups of order p, p2, pq, etc. M567 Introduction to Abstract Algebra II (Spring) Credits: 3 (3-0-0) Term Offered: Spring Text: Algebra by M. Artin Topics: - Rings: basic definitions, homomorphisms, ideals, quotient rings, adjunction of elements, integral domains, fraction fields, maximal ideals and algebraic geometry - Factorization: integers and polynomials, unique factorization domains, principal ideal domains, Euclidean domains, Gauss' Lemma, primes in Z[i], algebraic integers, real and imaginary quadratic fields, ideal factorization, ideal classes - Modules: matrices, free modules, bases, permanence of identities, diagonalization of integer matrices, generators and relations, application to abelian groups and linear operators, rational canonical and Jordan form, polynomial rings - Fields: algebraic and transcendental elements, field extensions and degree, ruler and compass constructions, finite fields, function fields - Galois Theory: quadratic, cubic, quartic, and quintic equations, symmetric functions, primitive elements, Kummer and cyclotomic extensions, the Galois group and the Galois correspondence. M570 Introduction to Topology Credits: 3 (3-0-0) Term Offered: Fall Prerequisites: Undergraduate courses in analysis and algebra such as M317-18 and M366. Topics: Topologies, topological spaces, continuous functions, homeomorphisms, metric spaces, compactness, connectedness, quotient spaces, the fundamental group, covering spaces M571 Introduction to Algebraic topology Credits: 3 (3-0-0) Term Offered: Spring Prerequisite: M570 Topics: More on homotopy and covering spaces, CW complexes, homology, applications to analysis