Giter Club home page Giter Club logo

fgt's Introduction

fgt

GitHub Workflow Status

Fast Gauss transforms.

The Gauss transform is a common operation that computes the per-point similarity between two data sets:

The Gauss transform

This a C++ library for computing the Gauss transform using the direct method as well as a few shortcuts. This code lives on Github and has some Doxygen documentation.

Usage

There is one C++ header file, fgt.hpp, which has everything you need. Include that file and you're off to the races:

#include <fgt.hpp>

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) 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:

#include <fgt.hpp>

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 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

Installation

fgt has no runtime dependencies, and only depends on CMake and Eigen for building.

Homebrew

If you're on a Mac and you use Homebrew, use my tap to install:

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:

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 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:

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.:

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:

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. 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.

This library was developed by Pete Gadomski, and it was inspired by the IFGT source code and figtree.

License

LGPL v2.1. See LICENSE.txt for the complete text.

fgt's People

Contributors

gadomski avatar hobu avatar puretryout avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

fgt's Issues

Check for cluster initialization

Since cluster construction and initialization are two different steps (since we need to first create the cluster structures, then populate the cluster via some sort of algorithm, then calculate a couple of things based upon those data populations), we need to check for cluster initialization wherever we use clusters.

Document installing against openmp

Since it is such a big performance win, it'd be nice to document how to build against openmp, especially on OSX.

As an aside, if we could get a homebrew install working with openmp that'd be even better, but that seems harder.

Rename X and Y to source and target

I thought about putting a comment in explaining the names. That means they should be named better. Same goes for h, rename it to bandwidth.

Protect against ludicrously big `p_max_total` values

E.g. if the maximum truncation number is 174 for 100-column datasets, p_max_total should be โ€” ridiculous. We should handle this exceptional case with an exception instead of going into undefined behavior.

Downgrade to cmake 3.0

PDAL's Docker-based dependencies only has cmake 3.0, and since we want to be usable in PDAL, we should downgrade our cmake version requirement.

Separate clusters from cluster factories

I took a step in the right direction when I separated things out into factories and clusters, but I didn't go all the way. The cluster factory should be the specialized part (Gonzales, etc), and the clustering itself should be relatively dumb. Doesn't have to be completely dumb, since we do need to call find_C, but dumber.

The clustering itself doesn't depend on the algorithm used to calculate it (at least for now).

Can we pre-compute coefficiants for the monomials?

We do the same loop a bunch of times for the monomial calculations. Sounds like a job for matrix math.

A complicating factor is that I'm not sure if the source and target monomials have the same number of terms. Check that.

Add data-adaptive ifgt

There's a version of IFGT that has a separate truncation number for every cluster. Let's try to throw that in, just for fun, in case it's faster for various applications.

Implement data-adaptive ifgt

This uses a per-point truncation number instead of a global one. This can speed things up a bit (but takes a little bit extra time to compute on the front end).

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.