-
Notifications
You must be signed in to change notification settings - Fork 1
/
preconditioner.html
40 lines (40 loc) · 24.9 KB
/
preconditioner.html
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
<!DOCTYPE html><html lang="en"><head><meta charset="utf-8" /><title>Preconditioners — PyMatting 1.1.10 documentation</title><link rel="stylesheet" href="/katex.min.css"><link rel="stylesheet" href="/style.css"><script src="/katex.min.js"></script></head><body><div class="sidebar"><div class="logo"><a href="/" class="sidebarlink"><img src="/figures/lemur_small.png" width="50px"></a><a href="/" class="logotext">PyMatting</a></div><div class="sidebarcontents">CONTENTS</div><ul><li><a href="/index.html" class="sidebarlink">PyMatting</a></li><li class="sidebarlink"><a href="/api.html" class="sidebarlink">API Reference</a><br><ul><li><a href="/alpha.html" class="sidebarlink">Alpha Estimation</a></li><li><a href="/cutout.html" class="sidebarlink">Cutout Function</a></li><li><a href="/foreground.html" class="sidebarlink">Foreground Estimation</a></li><li><a href="/laplacian.html" class="sidebarlink">Matting Laplacians</a></li><li><a href="/preconditioner.html" class="sidebarlink currentpage">Preconditioners</a></li><li><a href="/solver.html" class="sidebarlink">Solvers</a></li><li><a href="/util.html" class="sidebarlink">Utility Functions</a></li></ul></li><li><a href="/examples.html" class="sidebarlink">Examples</a></li><li><a href="/benchmarks.html" class="sidebarlink">Benchmarks</a></li><li><a href="/references.html" class="sidebarlink">Biblography</a></li><li><a href="https://pypi.org/project/PyMatting/" class="sidebarlink">PyPI</a></li><li><a href="https://www.github.com/pymatting/pymatting" class="sidebarlink">GitHub</a></li></ul></div><div class="middle"><h1>Preconditioners</h1><div><div class="function"><div id="ichol"><a href="https://github.com/pymatting/pymatting/blob/master/pymatting/preconditioner/ichol.py#L186-L303"><img src="/figures/github-mark.svg" title="Function definition on GitHub" class="github-icon"></a><h3 class="functionname">pymatting.ichol</h3><a href="#ichol" title="Permalink to this definition" class="functionanchorlink"> 🔗</a></div><div class="signature"><h4>Signature</h4><div class="signature"><div class="codeblock"><span class=name>ichol</span><span class=operator>(</span><span class=space>
</span><span class=name>A</span><span class=operator>,</span><span class=space>
</span><span class=name>discard_threshold</span><span class=operator>=</span><span class=number>1e-4</span><span class=operator>,</span><span class=space>
</span><span class=name>shifts</span><span class=operator>=</span><span class=operator>[</span><span class=number>0.0</span><span class=operator>,</span><span class=space> </span><span class=number>1e-4</span><span class=operator>,</span><span class=space> </span><span class=number>1e-3</span><span class=operator>,</span><span class=space> </span><span class=number>1e-2</span><span class=operator>,</span><span class=space> </span><span class=number>0.1</span><span class=operator>,</span><span class=space> </span><span class=number>0.5</span><span class=operator>,</span><span class=space> </span><span class=number>1.0</span><span class=operator>,</span><span class=space> </span><span class=number>10.0</span><span class=operator>,</span><span class=space> </span><span class=number>100</span><span class=operator>,</span><span class=space> </span><span class=number>1e3</span><span class=operator>,</span><span class=space> </span><span class=number>1e4</span><span class=operator>,</span><span class=space> </span><span class=number>1e5</span><span class=operator>]</span><span class=operator>,</span><span class=space>
</span><span class=name>max_nnz</span><span class=operator>=</span><span class=keyword>int</span><span class=operator>(</span><span class=number>4e9</span><span class=space> </span><span class=operator>/</span><span class=space> </span><span class=number>16</span><span class=operator>)</span><span class=operator>,</span><span class=space>
</span><span class=name>relative_discard_threshold</span><span class=operator>=</span><span class=number>0.0</span><span class=operator>,</span><span class=space>
</span><span class=name>diag_keep_discarded</span><span class=operator>=</span><span class=keyword>True</span><span class=operator>)</span></div></div></div><h4>Function Description</h4><div class="textblock"><span class="text">Implements the thresholded incomplete Cholesky decomposition.
For reference, a dense ichol implementation with relative threshold would look like this:</span></div><div class="code_block"><div class="codeblock"><span class=name>L</span><span class=space> </span><span class=operator>=</span><span class=space> </span><span class=name>np</span><span class=operator>.</span><span class=name>tril</span><span class=operator>(</span><span class=name>A</span><span class=operator>)</span><span class=space>
</span><span class=keyword>for</span><span class=space> </span><span class=name>j</span><span class=space> </span><span class=keyword>in</span><span class=space> </span><span class=keyword>range</span><span class=operator>(</span><span class=name>n</span><span class=operator>)</span><span class=operator>:</span><span class=space>
</span><span class=name>col</span><span class=space> </span><span class=operator>=</span><span class=space> </span><span class=name>L</span><span class=operator>[</span><span class=name>j</span><span class=operator>:</span><span class=operator>,</span><span class=space> </span><span class=name>j</span><span class=operator>]</span><span class=space>
</span><span class=name>col</span><span class=space> </span><span class=operator>-</span><span class=operator>=</span><span class=space> </span><span class=name>np</span><span class=operator>.</span><span class=keyword>sum</span><span class=operator>(</span><span class=name>L</span><span class=operator>[</span><span class=name>j</span><span class=operator>,</span><span class=space> </span><span class=operator>:</span><span class=name>j</span><span class=operator>]</span><span class=space> </span><span class=operator>*</span><span class=space> </span><span class=name>L</span><span class=operator>[</span><span class=name>j</span><span class=operator>:</span><span class=operator>,</span><span class=space> </span><span class=operator>:</span><span class=name>j</span><span class=operator>]</span><span class=operator>,</span><span class=space> </span><span class=name>axis</span><span class=operator>=</span><span class=number>1</span><span class=operator>)</span><span class=space>
</span><span class=name>discard_mask</span><span class=space> </span><span class=operator>=</span><span class=space> </span><span class=keyword>abs</span><span class=operator>(</span><span class=name>col</span><span class=operator>[</span><span class=number>1</span><span class=operator>:</span><span class=operator>]</span><span class=operator>)</span><span class=space> </span><span class=operator><</span><span class=space> </span><span class=name>relative_discard_threshold</span><span class=space> </span><span class=operator>*</span><span class=space> </span><span class=name>np</span><span class=operator>.</span><span class=keyword>sum</span><span class=operator>(</span><span class=name>np</span><span class=operator>.</span><span class=keyword>abs</span><span class=operator>(</span><span class=name>A</span><span class=operator>[</span><span class=name>j</span><span class=operator>:</span><span class=operator>,</span><span class=space> </span><span class=name>j</span><span class=operator>]</span><span class=operator>)</span><span class=operator>)</span><span class=space>
</span><span class=name>col</span><span class=operator>[</span><span class=number>1</span><span class=operator>:</span><span class=operator>]</span><span class=operator>[</span><span class=name>discard_mask</span><span class=operator>]</span><span class=space> </span><span class=operator>=</span><span class=space> </span><span class=number>0</span><span class=space>
</span><span class=name>col</span><span class=operator>[</span><span class=number>0</span><span class=operator>]</span><span class=space> </span><span class=operator>*</span><span class=operator>*</span><span class=operator>=</span><span class=space> </span><span class=number>0.5</span><span class=space>
</span><span class=name>col</span><span class=operator>[</span><span class=number>1</span><span class=operator>:</span><span class=operator>]</span><span class=space> </span><span class=operator>/</span><span class=operator>=</span><span class=space> </span><span class=name>col</span><span class=operator>[</span><span class=number>0</span><span class=operator>]</span></div></div><h4>Parameters</h4><ul><li class="parameteritem"><span class="parameter">A</span> (<i>scipy.sparse.csc_matrix</i>)<ul><div class="parameterdescription"><span class="text">Matrix for which the preconditioner should be calculated</span></div></ul></li><li class="parameteritem"><span class="parameter">discard_threshold</span> (<i>float</i>)<ul><div class="parameterdescription"><span class="text">Values having an absolute value smaller than this threshold will be discarded while calculating the Cholesky decompositions</span></div></ul></li><li class="parameteritem"><span class="parameter">shifts</span> (<i>array of floats</i>)<ul><div class="parameterdescription"><span class="text">Values to try for regularizing the matrix of interest in case it is not positive definite after discarding the small values</span></div></ul></li><li class="parameteritem"><span class="parameter">max_nnz</span> (<i>int</i>)<ul><div class="parameterdescription"><span class="text">Maximum number of non-zero entries in the Cholesky decomposition. Defaults to 250 million, which should usually be around 4 GB.</span></div></ul></li><li class="parameteritem"><span class="parameter">relative_discard_threshold</span> (<i>float</i>)<ul><div class="parameterdescription"><span class="text">Values with an absolute value of less than </span><span class="inline_code"><span class="codeinline"><span class=name>relative_discard_threshold</span><span class=space> </span><span class=operator>*</span><span class=space> </span><span class=keyword>sum</span><span class=operator>(</span><span class=keyword>abs</span><span class=operator>(</span><span class=name>A</span><span class=operator>[</span><span class=name>j</span><span class=operator>:</span><span class=operator>,</span><span class=space> </span><span class=name>j</span><span class=operator>]</span><span class=operator>)</span><span class=operator>)</span></span></span><span class="text"> will be discarded.</span></div></ul></li><li class="parameteritem"><span class="parameter">diag_keep_discarded</span> (<i>bool</i>)<ul><div class="parameterdescription"><span class="text">Whether to update the diagonal with the discarded values. Usually better if </span><span class="inline_code"><span class="codeinline"><span class=keyword>True</span></span></span><span class="text">.</span></div></ul></li></ul><h4>Returns</h4><ul><li class="parameteritem"><span class="parameter">chol</span> (<i>CholeskyDecomposition</i>)<ul><div class="parameterdescription"><span class="text">Preconditioner or solver object.</span></div></ul></li></ul><h4>Raises</h4><ul><li class="parameteritem"><span class="parameter">ValueError</span><ul><div class="parameterdescription"><span class="text">If inappropriate parameter values were passed</span></div></ul></li></ul><div class="block"><h4>Example</h4><div class="code_block"><div class="codeblock"><span class=indentation>>>> </span><span class=keyword>from</span><span class=space> </span><span class=name>pymatting</span><span class=space> </span><span class=keyword>import</span><span class=space> </span><span class=operator>*</span><span class=space>
</span><span class=indentation>>>> </span><span class=keyword>import</span><span class=space> </span><span class=name>numpy</span><span class=space> </span><span class=keyword>as</span><span class=space> </span><span class=name>np</span><span class=space>
</span><span class=indentation>>>> </span><span class=keyword>from</span><span class=space> </span><span class=name>scipy</span><span class=operator>.</span><span class=name>sparse</span><span class=space> </span><span class=keyword>import</span><span class=space> </span><span class=name>csc_matrix</span><span class=space>
</span><span class=indentation>>>> </span><span class=name>A</span><span class=space> </span><span class=operator>=</span><span class=space> </span><span class=name>np</span><span class=operator>.</span><span class=name>array</span><span class=operator>(</span><span class=operator>[</span><span class=operator>[</span><span class=number>2.0</span><span class=operator>,</span><span class=space> </span><span class=number>3.0</span><span class=operator>]</span><span class=operator>,</span><span class=space> </span><span class=operator>[</span><span class=number>3.0</span><span class=operator>,</span><span class=space> </span><span class=number>5.0</span><span class=operator>]</span><span class=operator>]</span><span class=operator>)</span><span class=space>
</span><span class=indentation>>>> </span><span class=name>cholesky_decomposition</span><span class=space> </span><span class=operator>=</span><span class=space> </span><span class=name>ichol</span><span class=operator>(</span><span class=name>csc_matrix</span><span class=operator>(</span><span class=name>A</span><span class=operator>)</span><span class=operator>)</span><span class=space>
</span><span class=indentation>>>> </span><span class=name>cholesky_decomposition</span><span class=operator>(</span><span class=name>np</span><span class=operator>.</span><span class=name>array</span><span class=operator>(</span><span class=operator>[</span><span class=number>1.0</span><span class=operator>,</span><span class=space> </span><span class=number>2.0</span><span class=operator>]</span><span class=operator>)</span><span class=operator>)</span><span class=space>
</span><span class=name>array</span><span class=operator>(</span><span class=operator>[</span><span class=operator>-</span><span class=number>1</span><span class=operator>.</span><span class=operator>,</span><span class=space> </span><span class=number>1</span><span class=operator>.</span><span class=operator>]</span><span class=operator>)</span></div></div></div></div></div><div><div class="function"><div id="L"><a href="https://github.com/pymatting/pymatting/blob/master/pymatting/preconditioner/ichol.py#L165-L175"><img src="/figures/github-mark.svg" title="Function definition on GitHub" class="github-icon"></a><h3 class="functionname">pymatting.CholeskyDecomposition.L</h3><a href="#L" title="Permalink to this definition" class="functionanchorlink"> 🔗</a></div><div class="signature"><h4>Signature</h4><div class="signature"><div class="codeblock"><span class=name>L</span><span class=operator>(</span><span class=name>self</span><span class=operator>)</span></div></div></div><h4>Function Description</h4><div class="textblock"><span class="text">Returns the Cholesky factor</span></div><h4>Returns</h4><ul><li class="parameteritem"><span class="parameter">L</span> (<i>scipy.sparse.csc_matrix</i>)<ul><div class="parameterdescription"><span class="text">Cholesky factor</span></div></ul></li></ul></div></div><div><div class="function"><div id="jacobi"><a href="https://github.com/pymatting/pymatting/blob/master/pymatting/preconditioner/jacobi.py#L1-L31"><img src="/figures/github-mark.svg" title="Function definition on GitHub" class="github-icon"></a><h3 class="functionname">pymatting.jacobi</h3><a href="#jacobi" title="Permalink to this definition" class="functionanchorlink"> 🔗</a></div><div class="signature"><h4>Signature</h4><div class="signature"><div class="codeblock"><span class=name>jacobi</span><span class=operator>(</span><span class=name>A</span><span class=operator>)</span></div></div></div><h4>Function Description</h4><div class="textblock"><span class="text">Compute the Jacobi preconditioner function for the matrix A.</span></div><h4>Parameters</h4><ul><li class="parameteritem"><span class="parameter">A</span> (<i>np.array</i>)<ul><div class="parameterdescription"><span class="text">Input matrix to compute the Jacobi preconditioner for.</span></div></ul></li></ul><h4>Returns</h4><ul><li class="parameteritem"><span class="parameter">precondition_matvec</span> (<i>function</i>)<ul><div class="parameterdescription"><span class="text">Function which applies the Jacobi preconditioner to a vector</span></div></ul></li></ul><div class="block"><h4>Example</h4><div class="code_block"><div class="codeblock"><span class=indentation>>>> </span><span class=keyword>from</span><span class=space> </span><span class=name>pymatting</span><span class=space> </span><span class=keyword>import</span><span class=space> </span><span class=operator>*</span><span class=space>
</span><span class=indentation>>>> </span><span class=keyword>import</span><span class=space> </span><span class=name>numpy</span><span class=space> </span><span class=keyword>as</span><span class=space> </span><span class=name>np</span><span class=space>
</span><span class=indentation>>>> </span><span class=name>A</span><span class=space> </span><span class=operator>=</span><span class=space> </span><span class=name>np</span><span class=operator>.</span><span class=name>array</span><span class=operator>(</span><span class=operator>[</span><span class=operator>[</span><span class=number>2</span><span class=operator>,</span><span class=space> </span><span class=number>3</span><span class=operator>]</span><span class=operator>,</span><span class=space> </span><span class=operator>[</span><span class=number>3</span><span class=operator>,</span><span class=space> </span><span class=number>5</span><span class=operator>]</span><span class=operator>]</span><span class=operator>)</span><span class=space>
</span><span class=indentation>>>> </span><span class=name>preconditioner</span><span class=space> </span><span class=operator>=</span><span class=space> </span><span class=name>jacobi</span><span class=operator>(</span><span class=name>A</span><span class=operator>)</span><span class=space>
</span><span class=indentation>>>> </span><span class=name>preconditioner</span><span class=operator>(</span><span class=name>np</span><span class=operator>.</span><span class=name>array</span><span class=operator>(</span><span class=operator>[</span><span class=number>1</span><span class=operator>,</span><span class=space> </span><span class=number>2</span><span class=operator>]</span><span class=operator>)</span><span class=operator>)</span><span class=space>
</span><span class=name>array</span><span class=operator>(</span><span class=operator>[</span><span class=number>0.5</span><span class=operator>,</span><span class=space> </span><span class=number>0.4</span><span class=operator>]</span><span class=operator>)</span></div></div></div></div></div><div><div class="function"><div id="vcycle"><a href="https://github.com/pymatting/pymatting/blob/master/pymatting/preconditioner/vcycle.py#L103-L153"><img src="/figures/github-mark.svg" title="Function definition on GitHub" class="github-icon"></a><h3 class="functionname">pymatting.vcycle</h3><a href="#vcycle" title="Permalink to this definition" class="functionanchorlink"> 🔗</a></div><div class="signature"><h4>Signature</h4><div class="signature"><div class="codeblock"><span class=name>vcycle</span><span class=operator>(</span><span class=space>
</span><span class=name>A</span><span class=operator>,</span><span class=space>
</span><span class=name>shape</span><span class=operator>,</span><span class=space>
</span><span class=name>num_pre_iter</span><span class=operator>=</span><span class=number>1</span><span class=operator>,</span><span class=space>
</span><span class=name>num_post_iter</span><span class=operator>=</span><span class=number>1</span><span class=operator>,</span><span class=space>
</span><span class=name>omega</span><span class=operator>=</span><span class=number>0.8</span><span class=operator>,</span><span class=space>
</span><span class=name>direct_solve_size</span><span class=operator>=</span><span class=number>64</span><span class=operator>,</span><span class=space>
</span><span class=name>cache</span><span class=operator>=</span><span class=keyword>None</span><span class=operator>)</span></div></div></div><h4>Function Description</h4><div class="textblock"><span class="text">Implements the V-Cycle preconditioner.
The V-Cycle solver was recommended by </span><span class="citation"><a href="/references.html#LW14">[LW14]</a></span><span class="text"> to solve the alpha matting problem.</span></div><h4>Parameters</h4><ul><li class="parameteritem"><span class="parameter">A</span> (<i>numpy.ndarray</i>)<ul><div class="parameterdescription"><span class="text">Input matrix</span></div></ul></li><li class="parameteritem"><span class="parameter">shape</span> (<i>tuple of ints</i>)<ul><div class="parameterdescription"><span class="text">Describing the height and width of the image</span></div></ul></li><li class="parameteritem"><span class="parameter">num_pre_iter</span> (<i>int</i>)<ul><div class="parameterdescription"><span class="text">Number of Jacobi iterations before each V-Cycle, defaults to 1</span></div></ul></li><li class="parameteritem"><span class="parameter">num_post_iter</span> (<i>int</i>)<ul><div class="parameterdescription"><span class="text">Number of Jacobi iterations after each V-Cycle, defaults to 1</span></div></ul></li><li class="parameteritem"><span class="parameter">omega</span> (<i>float</i>)<ul><div class="parameterdescription"><span class="text">Weight parameter for the Jacobi method. If method fails to converge, try different values.</span></div></ul></li></ul><h4>Returns</h4><ul><li class="parameteritem"><span class="parameter">precondition</span> (<i>function</i>)<ul><div class="parameterdescription"><span class="text">Function which applies the V-Cycle preconditioner to a vector</span></div></ul></li></ul><div class="block"><h4>Example</h4><div class="code_block"><div class="codeblock"><span class=indentation>>>> </span><span class=keyword>from</span><span class=space> </span><span class=name>pymatting</span><span class=space> </span><span class=keyword>import</span><span class=space> </span><span class=operator>*</span><span class=space>
</span><span class=indentation>>>> </span><span class=keyword>import</span><span class=space> </span><span class=name>numpy</span><span class=space> </span><span class=keyword>as</span><span class=space> </span><span class=name>np</span><span class=space>
</span><span class=indentation>>>> </span><span class=keyword>from</span><span class=space> </span><span class=name>scipy</span><span class=operator>.</span><span class=name>sparse</span><span class=space> </span><span class=keyword>import</span><span class=space> </span><span class=name>csc_matrix</span><span class=space>
</span><span class=indentation>>>> </span><span class=name>A</span><span class=space> </span><span class=operator>=</span><span class=space> </span><span class=name>np</span><span class=operator>.</span><span class=name>array</span><span class=operator>(</span><span class=operator>[</span><span class=operator>[</span><span class=number>2</span><span class=operator>,</span><span class=space> </span><span class=number>3</span><span class=operator>]</span><span class=operator>,</span><span class=space> </span><span class=operator>[</span><span class=number>3</span><span class=operator>,</span><span class=space> </span><span class=number>5</span><span class=operator>]</span><span class=operator>]</span><span class=operator>)</span><span class=space>
</span><span class=indentation>>>> </span><span class=name>preconditioner</span><span class=space> </span><span class=operator>=</span><span class=space> </span><span class=name>vcycle</span><span class=operator>(</span><span class=name>A</span><span class=operator>,</span><span class=space> </span><span class=operator>(</span><span class=number>2</span><span class=operator>,</span><span class=space> </span><span class=number>2</span><span class=operator>)</span><span class=operator>)</span><span class=space>
</span><span class=indentation>>>> </span><span class=name>preconditioner</span><span class=operator>(</span><span class=name>np</span><span class=operator>.</span><span class=name>array</span><span class=operator>(</span><span class=operator>[</span><span class=number>1</span><span class=operator>,</span><span class=space> </span><span class=number>2</span><span class=operator>]</span><span class=operator>)</span><span class=operator>)</span><span class=space>
</span><span class=name>array</span><span class=operator>(</span><span class=operator>[</span><span class=operator>-</span><span class=number>1</span><span class=operator>.</span><span class=operator>,</span><span class=space> </span><span class=number>1</span><span class=operator>.</span><span class=operator>]</span><span class=operator>)</span></div></div></div></div></div><footer>© Copyright 2023, Thomas Germer, Tobias Uelwer, Stefan Conrad, Stefan Harmeling</footer></div><script src="/auto-render.min.js" onload="renderMathInElement(document.body)"></script></body></html>