cmjiang.github.io/fsi.html at master · cmjiang/cmjiang.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
  "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<meta name="generator" content="jemdoc, see http://jemdoc.jaboc.net/" />
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<link rel="stylesheet" href="templates/jemdoc.css" type="text/css" />
<link rel="icon" href="templates/icon.jpg" />
<title>FSI</title>
<!-- MathJax -->
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
	  TeX: { equationNumbers: { autoNumber: "AMS" } }
});
</script>
<!-- End MathJax -->
</head>
<body>
<div id="layout-content">
<div id="toptitle">
<h1>FSI</h1>
<div id="subtitle"> A fast selected inversion algorithm.</div>
</div>
<h2>Description</h2>
<ul>
<li>
<p>Consider a normalized block <i>p-cyclic</i> matrix</p>
<p style="text-align:center">
\begin{equation} \label{eq:M}
M = \begin{bmatrix}
     I   &        &        & B_1 \\
    -B_2 &   I    &        &     \\
         & \ddots & \ddots &     \\
         &        & -B_L   & I    \\
\end{bmatrix},
\end{equation}
</p>
<p>
FSI computes a selected inversion of \(G = M^{-1}\).
</p>
</li>
<li>
<p>The selected inversion is a collection of selected blocks of \(G\). For example, given two integers \(c\) (\(L\%c = 0\)) and \(q\in[0,c-1]\), FSI computes \(L/c\) selected block columns
<p style="text-align:center">
\begin{equation}\label{eq:S}
\mathcal{S} = \{G_{k\ell}\, |\, 1 \leq k \leq L \,\, \mbox{and}
\,\, \ell \in \mathcal{I}\}
\end{equation}
</p>
<p>where \(\mathcal{I} = \{ c-q,\, 2c-q,\, \ldots,\, (L/c)c-q\}\).
</p>
<p>(The selected inversion is not limited to block columns. For more patterns please see the Reference [1].)
</p>
</li>
<li><p>FSI algorithm consists of three steps:</p>
<ol>
<li><p>Clustering: block cyclic reduction (BCR);</p>
<li><p>Inversion: block structured orthogonal factorization and inversion
(BSOFI);</p>
<li><p>Wrapping: seeds + adjacency relations \(\rightarrow\) selected inversion.</p>
</ol>
<p style="text-align:center;">
<img src="fsi/FsiAlg.png" alt="FSI Algorithm" width="400px">
</p>
<p><center>
Fig.1: Graphical illustration of the three stages of the FSI algorithm.
<center></p>
</li>
</ul>
<h2>Software</h2>
<ul>
<li>
<p><a href="https://github.com/cmjiang/FSI">Fortran 90 MPI/OpenMP hybrid parallel implementation of FSI algorithm on GitHub.</a></p>
</li>
<li>
<p><a href="http://quest.ucdavis.edu/">QUantum Electron Simulation Toolbox.</a></p>
</li>
</ul>
<h2>Examples</h2>
<ul>
<li><p>Parallel application on computing Green's functions in many-body Quantum Monte Carlo Simulations. Details in Ref.[1, 2, 3].<p>
<table class="imgtable"><tr>
<td><img src="fsi/omp.png" alt="omp.png" width="300px"/></td>
<td><img src="fsi/hybrid.png" alt="hybrid.png" width="300"/></td>
<td><img src="fsi/dqmc.png" alt="dqmc.png" width="300px" /></td>
</tr></table>
<p><center>
Fig.2 : Left: FSI Performance with OpenMP; Middle: FSI Performance with OpenMP/MPI; Right: Runtime of DQMC
</center>  </p>
</li>
</ul>
<h2>References</h2>
<ol>
<li><p>Chengming Jiang, Zhaojun Bai and Richard Scalettar.
<b>A fast selected inversion algorithm for Green's function calculation in many-body quantum Monte Carlo simulations</b>.
In <i>Proceedings of the 30th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2016)</i>, pp. 473&ndash;482, 2016.
(<a href="publications/ipdps2016.pdf">preprint</a>)</p></li>
<li>Talk at <a href="http://www.ipdps.org/ipdps2016/index.html">International Parallel and Distributed Processing Symposium (IPDPS) 2016</a>. (<a href="fsi/ipdps2016talk.pdf">slides</a>)</li>
<li>Poster at (1) <a href="https://www.siam.org/meetings/la15/">SIAM Conference on Applied Linear Algebra 2015</a> and (2) <a href="https://sites.google.com/a/lbl.gov/bascd-2015/">Bay Area Scientific Computing Day (BASCD) 2015</a>. (<a href="fsi/siam2015.pdf">poster</a>)</li>
</ol>
<h2>Contact</h2>
<ul>
<li> Email: cmjiang at ucdavis.edu</li>
<li> Homepage: <a href="http://cmjiang.cs.ucdavis.edu"> http://cmjiang.cs.ucdavis.edu </a>
</li>
</ul>
</div>
</body>
</html>