**diff options**

author | Ulrich Bauer <mail@ulrich-bauer.org> | 2015-10-01 09:33:04 +0000 |
---|---|---|

committer | Ulrich Bauer <ulrich.bauer@tum.de> | 2015-10-28 10:25:44 +0100 |

commit | 41a3fef94446ec6ce115c65d92890ae9b888690c (patch) | |

tree | cbb02e09115fbdaa9f414c4869423c90a39f57fc | |

parent | 5e17291ec6e6cdfe4c119239b993a30eff7a6f9e (diff) |

readme

-rw-r--r-- | README | 135 | ||||

-rw-r--r-- | README.md | 141 |

2 files changed, 141 insertions, 135 deletions

@@ -1,135 +0,0 @@ -=PHAT (Persistent Homology Algorithm Toolbox), v1.4.0= -Copyright 2013, 2014 IST Austria - -==Project Founders:== - -Ulrich Bauer, Michael Kerber, Jan Reininghaus - -==Contributors:== - -Hubert Wagner, Primoz Skraba - -==Downloads:== - * [https://drive.google.com/uc?id=0B7Yz6TPEpiGEMGFNQ3FPX3ltelk&export=download PHAT, v1.3.0] - * [https://drive.google.com/uc?id=0B7Yz6TPEpiGENE9KUnhUSFdFQUk&export=download PHAT, v1.2.1] - * [https://drive.google.com/uc?id=0B7Yz6TPEpiGERGZFbjlXaUt1ZWM&export=download benchmark data] - -==Description:== - -This software library contains methods for computing the persistence pairs of a -filtered cell complex represented by an ordered boundary matrix with Z<sub>2</sub> coefficients. -For an introduction to persistent homology, see the textbook `[1]`. This software package -contains code for several algorithmic variants: - - * The "standard" algorithm (see `[1]`, p.153) - * The "row" algorithm from `[2]` (called pHrow in there) - * The "twist" algorithm, as described in `[3]` (default algorithm) - * The "chunk" algorithm presented in `[4]` - -The last two algorithms exploit the special structure of the boundary matrix -to take shortcuts in the computation. The chunk algorithm makes use of multiple -CPU cores if it is compiled with OpenMP support. - -All algorithms are implemented as functor classes that manipulate a given {{{boundary_matrix}}} (to be defined below) object to reduced form. -From this reduced form one can then easily extract the persistence pairs. -Alternatively, one can use the {{{compute_persistence_pairs function}}} which takes an algorithm as a template parameter, reduces the given {{{boundary_matrix}}} and stores the resulting pairs in a given {{{persistence_pairs}}} object. - -The {{{boundary_matrix class}}} takes a "Representation" class as template parameter. This representation defines -how columns of the matrix are represented and how low-level operations -(e.g., column additions) are performed. The right choice of the representation -class can be as important for the performance of the program as choosing the -algorithm. We provide the following choices of representation classes: - - * {{{vector_vector}}}: Each column is represented as a sorted {{{std::vector}}} of integers, containing the indices of the non-zero entries of the column. The matrix itself is a {{{std::vector}}} of such columns. - * {{{vector_heap}}}: Each column is represented as a heapified {{{std::vector}}} of integers, containing the indices of the non-zero entries of the column. The matrix itself is a {{{std::vector}}} of such columns. - * {{{vector_set}}}: Each column is a {{{std::set}}} of integers, with the same meaning as above. The matrix is stored as a {{{std::vector}}} of such columns. - * {{{vector_list}}}: Each column is a sorted {{{std::list}}} of integers, with the same meaning as above. The matrix is stored as a {{{std::vector}}} of such columns. - * {{{sparse_pivot_column}}}: The matrix is stored as in the vector_vector representation. However, when a column is manipulated, it is first converted into a {{{std::set}}}, using an extra data field called the "pivot column". When another column is manipulated later, the pivot column is converted back to the {{{std::vector}}} representation. This can lead to significant speed improvements when many columns are added to a given pivot column consecutively. In a multicore setup, there is one pivot column per thread. - * {{{heap_pivot_column}}}: The same idea as in the sparse version. Instead of a {{{std::set}}}, the pivot column is represented by a {{{std::priority_queue}}}. - * {{{full_pivot_column}}}: The same idea as in the sparse version. However, instead of a {{{std::set}}}, the pivot column is expanded into a bit vector of size n (the dimension of the matrix). To avoid costly initializations, the class remembers which entries have been manipulated for a pivot column and updates only those entries when another column becomes the pivot. - * {{{bit_tree_pivot_column}}} (default representation): Similar to the {{{full_pivot_column}}} but the implementation is more efficient. Internally it is a bit-set with fast iteration over nonzero elements, and fast access to the maximal element. - -There are two ways to interface with the library: - - * using files: - # write the boundary matrix / filtration into a file "input" (see below for the file format). - # compile {{{src/phat.cpp}}} and run it: - {{{ - phat [--ascii] input output - }}} - # read the resulting persistence pairs into your program - - * using the C++ library interface: - # include all headers found in {{{src/phat.cpp}}} - # define a boundary matrix object, e.g. -{{{ -phat::boundary_matrix< bit_tree_pivot_column > boundary_matrix; -}}} - # set the number of columns: -{{{ -boundary_matrix.set_num_cols(...); -}}} - # initialize each column using -{{{ -boundary_matrix.set_col(...) -boundary_matrix.set_dim(...) -}}} - # define an object to hold the result: -{{{ -phat::persistence_pairs pairs; -}}} - # run an algorithm like this: -{{{ -phat::compute_persistence_pairs< phat::twist_reduction >( pairs, boundary_matrix ); -}}} - # examine the result: -{{{ -pairs.get_num_pairs() -pairs.get_pair(...) -}}} - - A simple example that demonstrates this functionality can be found in {{{src/simple_example.cpp}}} - -==File Formats:== - -The library supports input and output in ascii and binary format -through the methods {{{[load|save]_[ascii|binary]}}} in the classes {{{boundary_matrix}}} -and {{{persistence_pairs}}}. The file formats are defined as follows: - -{{{boundary_matrix}}} - ascii: - The file represents the filtration of the cell complex, containing one cell - per line (empty lines and lines starting with "#" are ignored). A cell is given by - a sequence of integers, separated by spaces, where the first integer denotes the - dimension of the cell, and all following integers give the indices - of the cells that form its boundary (the index of a cell is its position - in the filtration, starting with 0). - A sample file {{{single_triangle.dat}}} can be found in the examples folder. - -{{{boundary_matrix}}} - binary: - In binary format, the file is simply interpreted as a sequence of 64 bit signed integer - numbers. The first number is interpreted as the number of cells of the complex. The - descriptions of the cells is expected to follow, with the first number representing the - dimension of the cell, the next number, say N, representing the size of the boundary, - followed by N numbers denoting the indices of the boundary cells. - A sample file {{{single_triangle.bin}}} can be found in the examples folder. - -{{{persistence_pairs}}} - ascii: - The file contains the persistence pairs, sorted by birth index. The first integer in the - file is equal to the number of pairs. It is followed by pairs of integers encode the - respective birth and death indices. - A sample file {{{single_triangle_persistence_pairs.dat}}} can be found in the examples folder. - -{{{persistence_pairs}}} - binary: - Same as ascii format, see above. Only now the integers are encoded as 64bit signed integers. - A sample file {{{single_triangle_persistence_pairs.bin}}} can be found in the examples folder. - -==Supported Platforms:== - * Visual Studio 2008 and 2012 (2010 untested) - * GCC version 4.4. and higher - -==References:== - - # H.Edelsbrunner, J.Harer: Computational Topology, An Introduction. American Mathematical Society, 2010, ISBN 0-8218-4925-5 - # V.de Silva, D.Morozov, M.Vejdemo-Johansson: Dualities in persistent (co)homology. Inverse Problems 27, 2011 - # C.Chen, M.Kerber: Persistent Homology Computation With a Twist. 27th European Workshop on Computational Geometry, 2011. - # U.Bauer, M.Kerber, J.Reininghaus: Clear and Compress: Computing Persistent Homology in Chunks. [http://arxiv.org/pdf/1303.0477.pdf arXiv:1303.0477]
\ No newline at end of file diff --git a/README.md b/README.md new file mode 100644 index 0000000..b953afa --- /dev/null +++ b/README.md @@ -0,0 +1,141 @@ +# PHAT (Persistent Homology Algorithm Toolbox), v1.4.0 # +Copyright 2013, 2014 IST Austria + +## Project Founders: ## + +Ulrich Bauer, Michael Kerber, Jan Reininghaus + +## Contributors: ## + +Hubert Wagner + +## Downloads: ## +* [PHAT, v1.4.0](https://drive.google.com/uc?id=0B7Yz6TPEpiGEWmNyeVFsNXgtUGc&export=download) +* [PHAT, v1.3.0](https://drive.google.com/uc?id=0B7Yz6TPEpiGEMGFNQ3FPX3ltelk&export=download) +* [PHAT, v1.2.1](https://drive.google.com/uc?id=0B7Yz6TPEpiGENE9KUnhUSFdFQUk&export=download) +* [benchmark data](https://drive.google.com/uc?id=0B7Yz6TPEpiGERGZFbjlXaUt1ZWM&export=download) +* [benchmark data 2](https://drive.google.com/uc?id=0B7Yz6TPEpiGEWE55X3RuM3JjZ3M&export=download) + +## Description: ## + +This software library contains methods for computing the persistence pairs of a +filtered cell complex represented by an ordered boundary matrix with Z<sub>2</sub> coefficients. +For an introduction to persistent homology, see the textbook `[1]`. This software package +contains code for several algorithmic variants: + + * The "standard" algorithm (see `[1]`, p.153) + * The "row" algorithm from `[2]` (called pHrow in that paper) + * The "twist" algorithm, as described in `[3]` (default algorithm) + * The "chunk" algorithm presented in `[4]` + * The "spectral sequence" algorithm (see `[1]`, p.166) + +All but the standard algorithm exploit the special structure of the boundary matrix +to take shortcuts in the computation. The chunk and the spectral sequence algorithms +make use of multiple CPU cores if PHAT is compiled with OpenMP support. + +All algorithms are implemented as function objects that manipulate a given +`boundary_matrix` (to be defined below) object to reduced form. +From this reduced form one can then easily extract the persistence pairs. +Alternatively, one can use the `compute_persistence_pairs function` which takes an +algorithm as a template parameter, reduces the given `boundary_matrix` and stores the +resulting pairs in a given `persistence_pairs` object. + +The `boundary_matrix` class takes a "Representation" class as template parameter. +This representation defines how columns of the matrix are represented and how +low-level operations (e.g., column additions) are performed. The right choice of the +representation class can be as important for the performance of the program as choosing +the algorithm. We provide the following choices of representation classes: + + * `vector_vector`: Each column is represented as a sorted `std::vector` of integers, containing the indices of the non-zero entries of the column. The matrix itself is a `std::vector` of such columns. + * `vector_heap`: Each column is represented as a heapified `std::vector` of integers, containing the indices of the non-zero entries of the column. The matrix itself is a `std::vector` of such columns. + * `vector_set`: Each column is a `std::set` of integers, with the same meaning as above. The matrix is stored as a `std::vector` of such columns. + * `vector_list`: Each column is a sorted `std::list` of integers, with the same meaning as above. The matrix is stored as a `std::vector` of such columns. + * `sparse_pivot_column`: The matrix is stored as in the vector_vector representation. However, when a column is manipulated, it is first converted into a `std::set`, using an extra data field called the "pivot column". When another column is manipulated later, the pivot column is converted back to the `std::vector` representation. This can lead to significant speed improvements when many columns are added to a given pivot column consecutively. In a multicore setup, there is one pivot column per thread. + * `heap_pivot_column`: The same idea as in the sparse version. Instead of a `std::set`, the pivot column is represented by a `std::priority_queue`. + * `full_pivot_column`: The same idea as in the sparse version. However, instead of a `std::set`, the pivot column is expanded into a bit vector of size n (the dimension of the matrix). To avoid costly initializations, the class remembers which entries have been manipulated for a pivot column and updates only those entries when another column becomes the pivot. + * `bit_tree_pivot_column` (default representation): Similar to the `full_pivot_column` but the implementation is more efficient. Internally it is a bit-set with fast iteration over nonzero elements, and fast access to the maximal element. + +There are two ways to interface with the library: + +* using files: + * write the boundary matrix / filtration into a file "input" (see below for the file format). + * compile `src/phat.cpp` and run it: + ` + phat [--ascii] input output + ` + * read the resulting persistence pairs into your program +* using the C++ library interface: + * include all headers found in `src/phat.cpp` + * define a boundary matrix object, e.g. +` +phat::boundary_matrix< bit_tree_pivot_column > boundary_matrix; +` + * set the number of columns: +` +boundary_matrix.set_num_cols(...); +` + * initialize each column using +` +boundary_matrix.set_col(...) +boundary_matrix.set_dim(...) +` + * define an object to hold the result: +` +phat::persistence_pairs pairs; +` + * run an algorithm like this: +` +phat::compute_persistence_pairs< phat::twist_reduction >( pairs, boundary_matrix ); +` + * examine the result: +` +pairs.get_num_pairs() +pairs.get_pair(...) +` + +A simple example that demonstrates this functionality can be found in `src/simple_example.cpp` + +## File Formats: ## + +The library supports input and output in ascii and binary format +through the methods `[load|save]_[ascii|binary]` in the classes `boundary_matrix` +and `persistence_pairs`. The file formats are defined as follows: + +* `boundary_matrix` - ascii: + The file represents the filtration of the cell complex, containing one cell + per line (empty lines and lines starting with "#" are ignored). A cell is given by + a sequence of integers, separated by spaces, where the first integer denotes the + dimension of the cell, and all following integers give the indices + of the cells that form its boundary (the index of a cell is its position + in the filtration, starting with 0). + A sample file `single_triangle.dat` can be found in the examples folder. + +* `boundary_matrix` - binary: + In binary format, the file is simply interpreted as a sequence of 64 bit signed integer + numbers. The first number is interpreted as the number of cells of the complex. The + descriptions of the cells is expected to follow, with the first number representing the + dimension of the cell, the next number, say N, representing the size of the boundary, + followed by N numbers denoting the indices of the boundary cells. + A sample file `single_triangle.bin` can be found in the examples folder. + +* `persistence_pairs` - ascii: + The file contains the persistence pairs, sorted by birth index. The first integer in the + file is equal to the number of pairs. It is followed by pairs of integers encode the + respective birth and death indices. + A sample file `single_triangle_persistence_pairs.dat` can be found in the examples folder. + +* `persistence_pairs` - binary: + Same as ascii format, see above. Only now the integers are encoded as 64bit signed integers. + A sample file `single_triangle_persistence_pairs.bin` can be found in the examples folder. + +Supported Platforms: + +* Visual Studio 2008 and 2012 (2010 untested) +* GCC version 4.4. and higher + +References: + +1. H.Edelsbrunner, J.Harer: Computational Topology, An Introduction. American Mathematical Society, 2010, ISBN 0-8218-4925-5 +2. V.de Silva, D.Morozov, M.Vejdemo-Johansson: Dualities in persistent (co)homology. Inverse Problems 27, 2011 +3. C.Chen, M.Kerber: Persistent Homology Computation With a Twist. 27th European Workshop on Computational Geometry, 2011. +4. U.Bauer, M.Kerber, J.Reininghaus: Clear and Compress: Computing Persistent Homology in Chunks. [http://arxiv.org/pdf/1303.0477.pdf arXiv:1303.0477]
\ No newline at end of file |