# fgt **Repository Path**: jingko/fgt ## Basic Information - **Project Name**: fgt - **Description**: No description available - **Primary Language**: Unknown - **License**: LGPL-2.1 - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-04-25 - **Last Updated**: 2024-04-25 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # fgt [![GitHub Workflow Status](https://img.shields.io/github/actions/workflow/status/gadomski/fgt/build.yml?style=for-the-badge)](https://github.com/gadomski/fgt/actions/workflows/build.yml) Fast Gauss transforms. The Gauss transform is a common operation that computes the per-point similarity between two data sets: ![The Gauss transform](img/gauss-transform.png) This a C++ library for computing the Gauss transform using the direct method as well as a few shortcuts. This code lives on [Github](https://github.com/gadomski/fgt) and has [some Doxygen documentation](http://gadomski.github.io/fgt). ## Usage There is one C++ header file, `fgt.hpp`, which has everything you need. Include that file and you're off to the races: ```cpp #include void my_great_function(const Eigen::MatrixXd& x, const Eigen::MatrixXd& y) { double bandwidth = 0.3; Eigen::VectorXd gauss_transform = fgt::direct(x, y, bandwidth); } ``` The library provides a few different ways to calculate the Gauss transform: - `fgt::direct` calculates the exact Gauss transform, and is the most accurate and the slowest option. - `fgt::direct_tree` tries to do less work by only considering "close" points, where "close" is defined by the bandwidth. The direct tree method works best for very small bandwidths. - `fgt::ifgt` uses the [Improved Fast Gauss Transform (pdf)](http://www.umiacs.umd.edu/~yangcj/papers/siam_fgt_v11.pdf) to speed up the calculation. IFGT is fast for large bandwidths but can break down for smaller bandwidths. There's also a class-based interface: ```cpp #include void my_great_function(const Eigen::MatrixXd& x, const Eigen::MatrixXd& y) { double bandwidth = 0.3; fgt::Direct direct(x, bandwidth); Eigen::VectorXd result = direct.compute(y); } ``` This lets you break up your transform into a pre-compute and a compute step, which can save you some cycles if you're re-using the same source dataset in a more advanced transform (e.g. direct_tree or ifgt). There is some benchmarking code available in the [bench](bench/) directory, which you can use to try to get a sense of the performance of the various modes. We found a crossover point at bandwidths of a bit more than 0.2 during local testing on a Mac laptop; YMMV. ![Benchmarks conducted on a random dataset on my personal Mac laptop](img/2016-03-01-clang-700.1.81.x86_64-apple-darwin15.3.0.png) ## Installation **fgt** has no runtime dependencies, and only depends on [CMake](https://cmake.org/) and [Eigen](http://eigen.tuxfamily.org/) for building. ### Homebrew If you're on a Mac and you use [Homebrew](http://brew.sh), use [my tap](https://github.com/gadomski/homebrew-gadomski) to install: ```sh brew tap gadomski/gadomski brew install fgt ``` ### From source To build **fgt** from source on a *nix system, clone the repository and execute the traditional CMake build incantation: ```sh git clone https://github.com/gadomski/fgt mkdir -p fgt/build cd fgt/build cmake .. make ``` **fgt** doesn't make any assumptions about whether you do or do not want shared libraries, so if you have a preference be sure to set `BUILD_SHARED_LIBS`. ### Eigen ordering Eigen, by default, stores matrices in column-major order, but **fgt** works with [row-major](https://en.wikipedia.org/wiki/Row-major_order) matrices. If you want to avoid extra copies, pass in row-major matrices to **fgt** functions. You can use the `fgt::Matrix` typedef to help: ```cpp fgt::Matrix my_matrix(1000, 3); // creates an uninitialized 1000x3 row-major matrix of doubles ``` ### OpenMP **fgt** comes with built-in OpenMP parallelization, which can lead to some significant speedups for large data sets. To enable OpenMP, make sure you're using an OpenMP-aware compiler (on OSX, you can get OpenMP clang via Homebrew: `brew install clang-omp`) and set the CMake variable `WITH_OPENMP` to ON, e.g.: ```sh CC=clang-omp CXX=clang-omp++ cmake .. -DWITH_OPENMP=ON make ``` This will build an OpenMP-enabled **fgt** library. ### Tests **fgt** comes with a unit-test suite. To run, simply execute `make test`. You probably want `CMAKE_BUILD_TYPE=Release`, otherwise the tests will take a while. ### Using in a downstream project When you install **fgt** on your system, you will also install a few CMake configuration files that make it easy to integrate this project into your downstream work. If **fgt** is installed to a traditional location (e.g. `/usr/local`), finding **fgt** might be as simple as including the following in your `CMakeLists.txt`: ```cmake find_package(Fgt REQUIRED) target_link_libraries(my-sweet-target PUBLIC Fgt::Library-C++ ) ``` The provided target, `Fgt::Library-C++`, should have its `INTERFACE_INCLUDE_DIRECTORIES` and other useful properties configured, so you shouldn't have to muck with anything else. If you've installed **fgt** to a non-standard location, you may need to use `Fgt_DIR` to find its CMake configuration files, or use `CMAKE_PREFIX_PATH` to point CMake at your non-standard install tree. ## Versioning We follow [semantic versioning](http://semver.org/). Versions have annotated tags following a `vMAJOR.MINOR.PATCH` naming convention. While we'll do our best to increment the `MINOR` version with all breaking changes, we can't guarantee anything until `MAJOR` hits 1 (per usual). ## Contributing As always, we welcome bug reports, features requests, and particularly pull requests via [Github](https://github.com/gadomski/fgt). This library was developed by [Pete Gadomski](https://github.com/gadomski), and it was inspired by [the IFGT source code](http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/Software/IFGT/IFGT_code.htm) and [figtree](https://github.com/vmorariu/figtree). ## License LGPL v2.1. See LICENSE.txt for the complete text.