Skip to content

GSoC_2015_project_linalg

Jump to bottom Edit New page
Heiko Strathmann edited this page Feb 22, 2016 · 20 revisions

linalg: Unifying Shogun's linear algebra

Note: This project is partly outdated, as some parts have been addressed during out GSoC pause year in 2015. This might be integrated under the GSoC 2016 Shogun detox project. The description is interesting nevertheless.

Mentors

Description

This venture was started as a part of one GSoC project last year. This year we aim at finalizing and polishing Shogun's internal library for linear algebra. The goal is explore modern C++ linear algebra libraries to exploit their CPU/GPU powered linear algebra operations for Shogun and in turn offer Shogun algorithm coders a simple, uniform backend independent interface that they can use for their linear algebra calls using those libraries. Rather than writing implementation against a particular backend (that we currently do using Eigen3, Lapack, ViennaCL and Shogun's native implementation), algorithms should be written against linalg. This allows to

  • change backends at compile time, and
  • in particular makes our algorithms independent of the current trend in linear algebra software.
  • It also will allow to put many operations on GPUs without having to change the implementation (to an extend).

The goal is not to write a complete linear algebra library on our own, but at least have some of the most-used linalg calls in our internal lib, such as

  • factorizing matrices
  • linear solvers
  • eigen solvers
  • applying the same operation to every element of a large matrix
  • dot products
  • various utilities (get/set diagonal, fill, get/set columns, matrix-vector multiplication, supporting block based operations etc)

Why this is cool

This project will massively increase both performance and sustainability of Shogun. We will get parallelism of many algorithms for free and at the same time open up ways for using different, better, backends (such as GPUs) in the future. It will furthermore allow to write algorithms without knowledge of backend internals. Nobody wants to deal with Lapack API directly ;)

Details

Presently, a handful of operations are there in linalg, spread over two different modules, Core and Redux.

  • The first target is to populate linalg with most-used linear algebra operations for both dense and sparse matrices. This includes figuring out a nice way to handle
    • element-wise operations
    • col/row-wise operations
    • in-place operations, using blocking techniques (useful for large matrices)
    • block-based operations while using different third party/native backend. We'll be using Eigen3, ViennaCL/OpenCL and (optionally) LAPACK. We don't want native implementation for each of these operations, just the ones we've already got. So in most cases native implementation would involve moving existing code from other parts of Shogun to linalg.
  • Most important part of this job is matrix factorization/linear solvers/eigen solvers. This requires some investigation on the benefits/disadvantages of storing the factorization results for successive linear/eigen solver calls. We want at least
    • Cholesky
    • QR
    • LU
    • Eigen
    • SVD (see issue 2526, 2527).
  • We'd like to have iterative solvers such as
    • Conjugate Gradient (CG)
    • Stabilized Bi-conjugate gradient (BiCG-stab)
  • A large part will be to read through Shogun's core algorithms and make them use the new interface. This is where you show off all the cool stuffs you did in GSoC :) Once we have that, the mop-up job is to remove the existing piece of linear algebra operations from SGMatrix and SGVector to make them lightweight.

Difficulty & Requirements

Medium. You need knowledge on

  • Advanced C/C++ (knowledge about C++11 is a plus). A reasonable level of comfort with templates, template specialization, partial specialization, traits, SFINAE, ability to read/write non-trivial template code
  • Numerical Linear algebra
  • Eigen3, LAPACK (src level familiarity is a plus)
  • GPU programming (OpenCL/ViennaCL)
  • Shogun algorithms
  • OpenMP [Optional]

Waypoints and initial work

  • First of all, make sure you can compile and install Shogun on your machine.
  • Eigen3, OpenCL/ViennaCL, Lapack/cblas has to be installed as well. They are available in most of the standard repos (use the devel pack)
  • Make sure all the linalg unit-tests are running on your machine.
  • Keep an eye on the Github issues page for related issues.

Useful resources

Add a custom footer
Clone this wiki locally