240 Arithmetic Analysis and Implementation Environments
Instructors
Lecturer C. Alexopoulos
Professor Th. Papatheodorou
Syllabus
Fundamental methods for the solution of non linear equations: bisection method, secant method and NewtonRaphson method. Numerical Linear Algebra methods for system solving: Gauss without pivoting, factorization, Cholesky and LU decomposition, error analysis and condition indicator of tables, classic iterative methods, as Jacobi, GaussSeidel, SOR, AOR.
Methods for the calculation of the eigenvalues. Interpolation and Polynomial Approximation. Interpolation methods with polynomials and partial polynomials (splines, Hermite).
Errors analysis and acceleration of convergence. Numerical differentiation and integration (rules of table, Simpson, Gauss).
Polynomial LeastSquares approximation. Fourier Series approximation. Numerical solution of one step regular differential equations and adaptive methods Euler, RungeKutta. Applications in Matlab, Fortran and Pascal.
Lesson Structure
Credit Units: 5
Lecture: 3 hours/week
Tutorial: 2 hours/week
Laboratory: 2 hours/week
.::Top::.
205 Introduction to Algorithms
Instructors
Assistant Professor C. Zaroliagis
Professor Th. Papatheodorou
Syllabus
It aims at introducing the students to fundamental algorithmic techniques and concepts. The following topics are covered. What is an algorithm, Graphs, Trees, Asymptotic Notation, Correctness, How good is an Algorithm, Optimal Algorithms, Usage of trees for analyzing algorithms, Lower bounds for searching and sorting arrays, An example of an optimal algorithm, The "heap" data structure and the Heapsort algorithm for sorting arrays, NP and NPcomplete problems, Reductions. Recursively Reducing problems into smaller sizes: the "Divide and Conquer" (D&C) approach. Analysis of the D&C approach, Examples, The Algorithm of Strassen for Matrix Multiplication, Sorting arrays using D&C methods. Quicksort, Shellsort, Bucket and Radix Sort Algorithms, Merging and the Mergesort Algorithm, Sorting on external devices, Solving Linear Systems with the OddEven reduction method. Fast Fourier Transformation (FFT): A quick review of the properties of complex numbers, Recursive FFT equations, Organization of the calculations, Complexity of FFT, Inverse FFT, FFT for real vectors. Convolution, Symbolic multiplication of polynomials, The Discrete Sine and Cosine Transformations, Applications for solving systems of equations. Graph Algorithms: Traversing Graphs, DepthFirst Search, BreadthFirst Search, Connected Components, Directed Acyclic Graphs and Topological Sorting, Strongly Connected Components, Biconnected Components, Matching. Greedy approaches for solving algorithms. Sorting tasks with deadlines, The Knapsack problem, Minimum Spanning Trees (algorithms of Prim and Kruskal), Dynamic Programming, The Shortest Path Problem, Backtracking. Iterative methods. Jacobi and GaussSeidel methods, Relaxation and the SOR method. Selected Topics: String matching, Preparation, heuristic Algorithms for designing chips.
Lesson Structure
Credit Unit: 5
Lecture: 3 hours/week
Tutorial: 1 hours/week
Laboratory: 2 hours/week
.::Top::.
343 Scientific Computing É
Instructors
Professor Ef. Gallopoulos
Professor Th. Papatheodorou
Syllabus
Modern computing systems and Scientific Computing. Technology and effects of memory hierarchy. High performance optimizing compilers. Performance monitoring and measurement.
Precision and roundoff errors. IEEE floating point arithmetic. Roundoff error analysis and relevant software. Matrix multiplication and blocking. BLAS hierarchy. Fast matrix multiplication methods.
Cholesky and LU decomposition and their application in linear system solving with emphasis in alternative organization of solution schemes. The LAPACK package.
Memory storage and solution of special linear systems: Banded matrices, Hessenberg matrices, block tridiagonal matrices, Vandermonde, Toeplitz, Hankel matrices. Polynomials and the irrelation to matrices of special structure.
Orthogonalization methods: Householder, GramSchmidt, Givens, block implementations and applications. Direct and iterative methods for the solution of large and sparse linear systems. Eigenvalue problems and differential equations.
Lesson Structure
Credit Unit: 5
Lecture: 3 hours/week
Tutorial: 1 hours/week
Laboratory: 2 hours/week
.::Top::.
440 Parallel Processing
Instructors
Professor Th.Papatheodorou
Syllabus
Introduction to parallel processing: Application requirements, Examples of parallelism, Interconnection infrastructure, Flynn classification in parallel architectures, Memory based classification, Performance metrics, Computation distribution, Degree of parallelism, Load balancing, Amdahl's law.
Main characteristics and examples of advanced architectures: SISD architectures, Very large instruction word (VLIW) systems, SIMD architectures, Array processors / Associative processors, MIMD architectures, Systolic arrays and wavefronts.
Pipelines and vector processors: Basic concepts, Vector instruction analysis, Arithmetic pipelines, Instruction pipelines, Example of pipeline design, Pipeline conflicts and throughput optimization.
Memory: Context addressable or associative memory, Cache memories, Overview of data placement policies, Memory coherence and consistency, Snoopy caches, Directory solutions, Software solutions, Hierarchical memory design, Memory multiplexing, Parallel access for vectors of processors, Data placement stride and access collisions for pipelines, Memory organization for vector processors.
Interconnection networks: Main concepts, Permutations, Single stage interconnection networks, Generalized hypercube network, Data manipulation networks, Multistage networks, SwBanyan networks, Omega network, Baseline network, Benes network, Batcher network for parallel merging, Theoretical analysis of multistage networks.
Lesson Structure
Credit Units: 3
Lecture: 2 hours/week
Tutorial: 1 hours/week
Laboratory: 3 hours/week
.::Top::.
443 Scientific Computing II
Instructors
Professor Ef. Gallopoulos
Professor Th. Papatheodorou
Professor Ç. Houstis
Syllabus
Structure and specifications of large scale computational problems. Sparse matrices. Numerical solution of large linear systems using classic iterative methods (Jacobi, SOR, SSOR), polynomial methods (Richardson, Chebyshev). Elements of projection methods. The Arnoldi iteration.
Krylov subspace methods: Lanczos, CG, FOM, GMRES and BiCG.
Numerical solution of differential equations: Discretization techniques and truncation errors. Fast elliptic linear solvers. Domain decomposition.
Multigrid methods. Fast multipole methods. Synergy and interaction of algorithms, applications, implementations and computing infrastructure for the development of efficient methods for large computational problems. Contemporary problem solving environments for Scientific Computing.
Lesson Structure
Credit Units: 3
Lecture: 2 hours/week
Tutorial: 1 hours/week
Laboratory: 2 hours/week
.::Top::.
540 Advanced Parallel Systems
Instructors
Professor Th. Papatheodorou
Lecturer E. Polychronopoulos
Syllabus
Fundamental software topics (synchronization, multithreading, restructuring compilers): Synchronization, Synchronization in shared memory systems, Synchronization in message passing systems, Communication latency overlapping, Multithreading, Restructuring compilers, Data dependencies and dependence analysis, Automatic vectorization and loop parallelization, Synchronization in "DOACROSS" loops, Languages, Compilers and Operating Systems.
Principles of application development: Loop programming techniques, Basic operations programming alternatives, Virtual memory aware programming, Programming nonhierarchical memory systems, Programming hierarchical memory systems, Basic linear algebra subroutines, SparseLib++ (C++ sparse array library), NetLib.
Communication in message passing architectures: Message passing mechanisms, Simple transmission, Communication patterns, Communication overhead upper bounds, Latency for specific communication patterns in torus and grid, Latency for specific communication patterns in hypercubes, Overview of results.
Techniques for attaining high performance and analysis of results under realworld circumstances: Problem and method description, Application environment, Communication, Parallel implementation and remarks, Analysis of results.
Lesson Structure
Credit Units: 3
Lecture: 2 hours/week
Tutorial: 1 hours/week
Laboratory: 3 hours/week
.::Top::.
545 Computational Methods for Differential Equations
Instructors
Professor Th. Papatheodorou
Professor I. Houstis
Lesson Structure
Credit Units: 3
Lecture: 2 hours/week
Tutorial: 1 hours/week
Laboratory: 3 hours/week
.::Top::.
131 Inroduction to Software
Instructors
Lecturer Å. Polyxronopoulos
Syllabus
Main goal of this lesson is to teach students the logic of structural programming and the methodology for developing programs. For this purpose language C has been choosen because it is flexible and offers the background for future lessons. Some basic themes of the lesson are: design, development, debbuging. Data types, Control Flow, basic functions, I/O, variables and scope, structs, pointers and files.
Lesson Structure
Credit Units: 3
Lecture: 2 hours/week
Tutorial: 2 hours/week
Laboratory: 2 hours/week
.::Top::.
131E Software Laboratory
Instructors
Lecturer Å. Polyxronopoulos
Syllabus
Consists of a range of exercises in C language. These exercises are being developed by the students in order to obtain a better understanding of what they are teached in the lesson.
Lesson Structure
Credit Units: 1
Laboratory: 2 hours/week
.::Top::.
Operating Systems Laboratory
Instructor
Lecturer Å. Polyxronopoulos
Syllabus
The design and development part of the kernel of a Unix like operating system running on a simulated hardware: Processes and their development, memory management, Spooling, Swapping, I/O tools, scheduling.
Lesson Structure
Credit Units: 2
Laboratory: 3 hours/week
.::Top::.
