fem

TEI - Introdução à Computação Científica Combinatorial - 09/1

Profas. Maria Claudia Silva Boeres e Lucia Catabriga

Programa

Problemas de Computação Científica de interesse
Formulação dos problemas de interesse em Combinatória

2.1 Isomorfismo de Grafos

2.2 Coloração de Grafos

2.3 Particionamento de Grafos

Estudo de Algoritmos

3.1 Isomorfismo de Grafos

3.2 Coloração de Grafos

3.3 Particionamento de Grafos

3.4 Teoria Espectral de Grafos

Horário das Aulas:
Quintas 17-20 hs

Avaliação:

Através de Seminários, Exercícios e Implementações

Notas de Aula

Aula 1: Problemas de Computação Científica de interesse
Aula 2 e 3: Formulação dos problemas de interesse em Combinatória
Aula 4 e 5: Seminários dos alunos sobre o artigo "Combinatorial Scientific Computing: The Enabling Power of Discrete Algorithms in Computational Science", Bruce Hendrickson and Alex Pothen.

Tarefas:

Seminários:

Data	Conteúdo	Responsáveis
16/04/09 e 23/04/09	Aplicações em Computação Científica Combinatorial: os alunos devem escolher um dos temas abaixo e preparar uma apresentação de 20 minutos baseada na referência [1]. Os temas listados são as seções do artigo. Lembramos que a leitura de outras referências é fundamental! Computação Paralela e Geração de Malhas (2 alunos) Sistemas Lineares Esparsos (2 alunos) Otimização, Derivação e Coloração (2 alunos) Física Estatística, Química Computacional e Bioinformática (1 aluno) Obs 1: Ao final desse seminário, os alunos devem escolher os temas de trabalho que serão abordados ao longo do restante do curso. Lembramos que os problemas de interesse identificados foram Isomorfismo de Grafos, Coloração de Grafos e Particionamento de Grafos.	Rafael e Leonardo=> Otimização, Derivação e Coloração Referências da apresentação do Leonardo: Ernesto Birgin (tese): http://libdigi.unicamp.br/document/?code=000133708 Coleman e Moré (1984): http://www.springerlink.com/content/936385j423n27j66/ Outras referências: http://www.cs.odu.edu/~cscapes/cscapes/acyclic-SISC.pdf http://www.ii.uib.no/publikasjoner/texrap/ps/1992-72.ps Kamila e Victor=> Computação Paralela e Geração de Malhas Renato e Rodrigo => Sistemas Lineares Esparsos
30/04/09	Algoritmos Multinível de Particionamento de Grafos	1) Kamila
07/05/09	Um algoritmo espectral para redução do envelope de matrizes esparsas	2) Leonardo
14/05/09	Heurísticas de Coloração de Grafos	3) Rafael
21/05/09	Um Algoritmo para geração de malhas implementado no MatLab	4) Victor
28/05/09	Estudo do desempenho do cálculo do Produto Matriz-Vetor Esparso	5) Rodrigo
04/06/09		6) Renato

Entrevistas:

Dia	Horário	Aluno
18/05/09	13:30-15:00	Victor e Rodrigo
18/05/09	15:00-16:00
21/05/09	16:00-17:00	Kamila
25/05/09	13:00-14:00	Renato
25/05/09	14:00-15:00	Rodrigo
28/05/09	16:00-17:00	Leonardo
01/06/09	13:00-14:00	Rafael
01/06/09	14:00-15:00	Victor
04/06/09	16:00-17:00	Renato
08/06/09	13:00-14:00	Rodrigo

Bibliografia Inicial

[1] Bruce Hendrickson and Alex Pothen, Combinatorial Scientific Computing: The Enabling Power of Discrete Algorithms in Computational Science, In Lecture Notes in Computer Science 4395:260-280, 2007.
[2] Bruce Hendrickson, Combinatorial Scientific Computing: The Role of Discrete Algorithms in Computational Science and Engineering, Plenary talk at SIAM CSE'03.
[3] Assefaw Hadish Gebremedhin, Fredrik Manne, Alex Pothen, What Color Is Your Jacobian? Graph Coloring for Computing Derivatives, SIAM REVIEW, 2005 Society for Industrial and Applied Mathematics, Vol. 47, No. 4, pp. 629–705.

[4] Ali Pınar, Michael T. Heath, Improving Performance of Sparse Matrix-Vector Multiplication, Proceedings of the ACM/IEEE SC99 Conference (SC’99), 1-58113-091-0/99
[5] Stephen T. Barnard, Alex Pothen, and Horst D. Simon, A Spectral Algorithm for Envelope Reduction of Sparse Matrices, Report RNR-93-015, October 1993, NAS Systems Division, Applied Research Branch NASA Ames Research Center, Mail Stop T045- Moffett Field, CA 94035 (submitted to Journal of Numerical Linear Algebra with Applications).

[6] Assefaw Hadish Gebremedhi, Practical Parallel Algorithms for Graph Coloring Problems in Numerical Optimization, P.H. Thesis, Department of Informatics University of Bergen, Norway, 2003.

[7] B. Hendrickson and T. Kolda. Graph partitioning models for parallel computing. Parallel Comput., 26:1519–1534, 2000.

[8] A.L. G. A. Coutinho, M. A. D. Martins, R. M. Sydenstricker, and R. N. Elias, Performance comparison of data-reordering algorithms
for sparse matrix–vector multiplication in edge-based unstructured grid computations, Int. J. Numer. Meth. Engng; 66:431–460, 2006.
[9] A. George, A. Pothen, AN ANALYSIS OF SPECTRAL ENVELOPE-REDUCTION VIA QUADRATIC ASSIGNMENT PROBLEMS. (Available on the Web at URL http://www.cs.odu.edu/~pothen/papers.html)

Links Interessantes

Página de Bruce Hendrickson: http://www.sandia.gov/~bahendr/
Página de James Demmel: http://www.eecs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html,
Página de Alex Pothen: http://www.cs.odu.edu/~pothen/papers.html
Página do Combinatorial Scientific Computing Lab: http://www.cs.ucsb.edu/~gilbert
Blog de Ciprian Zavoianu: http://ciprian-zavoianu.blogspot.com/2009/01/project-bandwidth-reduction_18.html
Benchmarks para coloração de grafos http://people.brunel.ac.uk/~mastjjb/jeb/orlib/colourinfo.html
http://mat.gsia.cmu.edu/COLOR/instances.html
Algoritmo Polinomial exato para resolução do problema de isomorfismo de grafos http://www.geocities.com/dharwadker/tevet/isomorphism/