PhD position in Computational Topology and Geometry at TU Graz

The Institute of Geometry at Graz University of Technology offers a PhD position in the newly established research area “Computational Topology and Geometry”. The focus lies on the emerging field of persistent homology, a theory that turns homological algebra robust to noise and has paved the way to the topological analysis of real-world data. Besides theoretical aspects, the group works on algorithmic tools in the context of this data analysis techniques, on the connections to low- and high-dimensional computational geometry, and on applications of topological data analysis.

We offer a 4-year university assistant position (30 h/week) with a net salary of approximately 20,000 EUR per year. The position is available starting October 1 2015, and should be filled as soon as possible. The position is integrated into the field of expertise “Information, Communication, and Computing” at TU Graz, providing a stimulating interdisciplinary research environment. The graduate school “Discrete Mathematics” additionally contributes to the quality of TU Graz as a research center.

We are looking for outstanding students with a master’s degree in Mathematics/Computer Science or a closely related field. Knowledge in at least one of the fields computational geometry, computational topology, or algebraic topology, and programming skills, in particular in C++, are desirable.

Applications should include:
* a letter of application and motivation
* a detailed curriculum vitae
* a reference letter (for instance, by the Master thesis supervisor)
* email addresses of additional references (if applicable)
* a preferred starting date

and should be sent until August 23, 2015 using the reference number 5070/15/007 to (email is enough):

Technische Universität Graz
Dekan der Fakultät für Mathematik, Physik und Geodäsie
Univ.-Prof. Dipl.-Phys. Dr.rer.nat. Wolfgang Ernst
Petersgasse 16
A-8010 Graz
bewerbungen.tmtph@tugraz.at

For further questions, please contact Michael Kerber (mkerber@mpi-inf.mpg.de).

Women in Computational Topology

Brittany Fasy writes:

Recently, a listserv for women in Computational Topology was initiated. The idea is that we can use this mailing list to remind each other about upcoming deadlines, find out who is going to SoCG or CCCG next year, etc. Feel free to encourage others (men or women) to join our network too! If you are interested in joining, send a blank email to <WinCompTop+subscribe@googlegroups.com>. If you have any trouble joining or posting to the listserv, please email Brittany <brittany@fasy.us>.

Exercises in Materials Geometry and Topology

********************************************
Shape Up 2015
Exercises in Materials Geometry and Topology

Berlin (Germany), 14-18 September 2015
********************************************

Dear Scientists and Mathematicians,

We wish to announce our upcoming conference:

Shape Up 2015

Exercises in Materials Geometry and Topology

The conference will be an interdisciplinary discussion meeting on
patterns and geometry, and their role in biological and synthetic
microstructured materials and tissue.. We invite contributions
from biology, chemistry, materials science, mathematics, physics
and related fields addressing the genesis, properties and function
of complex nano-scale geometries, as well as underlying geometric
and topological concepts for the study of complex structure and shape..

The key areas of interest include:

* Geometric and topological concepts in soft condensed matter
* Characterization of structure and function
* Topological data analysis and image reconstruction
* Self-assembly of bi- and polycontinuous phases
* Negatively curved surfaces and hyperbolic geometry
* Structure enumeration & network-like phases
* Function of complex nanostructures in biology
* Bio-inspired design of materials
* Knots and entanglements in physics
* Emergence of chirality, order and the role of disorder
* Symmetry, graphs and discrete geometry
* Tessellations, area-minimising foams and packings
* Three-dimensional topology of cellular microstructures
* Pattern formation and complex structures in soft materials

The conference will run from Monday morning 14 September 2015 to the
late afternoon of Friday 18 September and will feature an extended
poster session, 15-20 contributed talks as well as invited lectures
by

* Simon Copar (U Ljubljana)
* Herbert Edelsbrunner (IST Austria)
* Karsten Grosse-Brauckmann (TU Darmstadt)
* Jemal Guven (U Nacional Autonoma de Mexico)
* Stephen Hyde (Australian National University)
* Motoko Kotani (Tohoku U)
* Rob Kusner (UMass Amherst)
* Jeremy Mason (Bogazici U)
* Elisabetta Matsumoto (Harvard U)
* Konstantin Mischaikow (Rutgers U)
* Piotr Pieranski (U Poznan)
* James Sethian (UC Berkeley)
* Ullrich Steiner (U Fribourg)
* John M. Sullivan (TU Berlin)
* Adam Squires (U Reading)
* Salvatore Torquato (U Princeton)
* Silvia Vignolini (U Cambridge)

The conference is hosted at the Technical University of Berlin on
Strasse des 17. Juni that leads right up to the famous Brandenburg Gate,
next to Reichstag, the parliament of Germany. Museum Island, Berliner
Philharmonie, Opera Houses, Checkpoint Charlie, Berlin Television Tower
and other famous sites are within a few kilometers walking distance and
are easily accessible via public transport that connects all of inner
Berlin – from vibrant Prenzlauer Berg to Gendarmenmarkt at the heart
of Berlin. All lectures and the poster session will take place at the
Institute of Mathematics, Strasse des 17. Juni 136.

We are inviting abstracts for contributed oral presentations and for
posters. We encourage you to use the latex-template on the website
(http://www.shape-up.academy/) and to include both attractive images
and references in your abstract. The deadline for abstract submission
is

***  31 May 2015  ***

Registration will open 15 June 2015.

We are hopeful of encouraging people from a wide variety of scientific
and mathematical backgrounds to attend. Any queries can be addressed
to the organising committee at shape-up@math.tu-berlin.de.

Best regards, and we hope to see you in Berlin,

The Organising Committee

Myfanwy Evans (TU Berlin), Andrew Kraynik (Sandia, (Ret.)), Frank Lutz
(TU Berlin), Gerd Schroeder-Turk (Murdoch) and Bodo Wilts (Fribourg)

Special issue on "Algorithms and Software for Computational Topology"

…in the Journal of Symbolic Computation

Aim and Scope:

The interest in algorithms on topological problems and their implementation has rapidly grown during the last decade. One driving force is the emergence of “topological data analysis” which connects topological concepts like Morse theory and homology to the investigation of real-world data. Another recent track of research substantially expands the realm of possibility for computational approaches in 3-manifold and knot theory. Common to these and other developments is the ability to handle large data collections through an efficient algorithmic framework as well as mature software implementations of those. A workshop session at the International Congress of Mathematical Software (ICMS) in August 2014 was dedicated to this topic (http://icms14.appliedtopology.org/).

The Journal of Symbolic Computation (JSC) invites high-quality contributions from researchers in the area of Computational Topology reporting on original research achievements towards algorithms, software, and applications. The list of topics includes, but is not limited to

  • (Persistent) homology
  • Topological data analysis
  • 3-manifold topology and knot theory
  • (Discrete) Morse theory

Researchers which are unsure whether their contribution is suitable are encouraged to contact the guest editor.

Submission instructions:

It is recommended to prepare submission in the same format as regular submission to JSC (see the “Guide for Authors” at http://www.journals.elsevier.com/journal-of-symbolic-computation/).

The paper must start with a introduction that

  • clearly states the considered problem
  • discusses its relevance and related work
  • explains the main contribution of the paper
  • explains why the contribution is original and non-trivial

There is no page limit on submitted manuscripts. It is required, however, that

  • all related work is completely and carefully discussed
  • all theorems are rigorously proved
  • important definitions/theorems/algorithms are illustrated by well-chosen examples.

All submitted papers will be refereed according to the high standards of JSC.

Guest editor:

Michael Kerber (Max Planck Institute for Informatics) – mkerber@mpi-inf.mpg.de

Deadline:

The submission deadline is January 31 2015. The special issue is planned to appear in Fall 2015

AATRN Seminar: Robert Ghrist

Today, the promised AATRN seminar series got started with Robert Ghrist as the inaugural speaker. His lecture, through WebEx, builds up the cellular sheaf perspective on networks with capacity, Max Flow / Min Cut, and the work done by Ghrist, Yasu Hiraoka, and Sanjeevi Krishnan on categorifying and sheafifying MF/MC.

Among the novel insights coming from this talk even if one has been following the UPenn developments for a while was the connection to Poincare Duality: “Flow duality is a form of Poincare duality” — S. Krishnan

The approach detailed by Krishnan in his preprint (on http://www.math.upenn.edu/~sanjeevi/papers/mfmc.pdf ) encodes a flow network as a sheaf of semi-modules of capacities over a semi-ring over the directed graph of the network. Flows correspond to homology, cuts to cohomology.

MF/MC translates to:

Theorem (S. Krishnan)

Given a network X, a distinguished (virtual) edge e and a capacity sheaf F, (all) flowvalues at e of flows on F correspond to the homotopy limit over all cuts of cutvalues of cuts on F.

This approach, and connecting flows and cuts to a lattice structure on the constraints produces a setting where multi-kind flows can easily be analyzed with the same tools as ordinary flows, and where the algebra fixes the duality gaps that show up when naively searching for minima and maxima.

The talk culminated in a primer on the homology and cohomology of directed sheaves, to set us up to read Krishnan’s paper, constructing compact support cohomology and Borel-Moore homology for sheaves over directed spaces.

The added abstraction levels seem to enable MF/MC theorems for, for instance, probability distributions. It also carries a promise for insights into duality gaps in MF/MC type problems.

Applied Algebraic Topology Research Network

Peter Bubenik writes:

[…] Robert Ghrist, Konstantin
Mischaikow, Fadil Santosa and I are starting a Research Network in Applied Algebraic Topology. To start, the main activity of the network will be a weekly interactive online seminar. We have plans to expand our activities in the future.

Rob Ghrist will give the first talk on Tue Sept 23.

Please check out our web site at https://www.ima.umn.edu/topology/ and become a member.

Efficiently implementing the persistence algorithm

Around the time of my recent submission Multicore homology via Mayer Vietoris an interesting optimization was made which seems to have a nice impact on the running time of the persistence algorithm.

When computing persistence  the boundary matrix is usually stored sparsely. In particular, over \mathbb{Z}_2 each column stores only the indices of the rows of the matrix which are nonzero in it’s column.

In the parlance of [ZC ’05]  each column is identified as:

x = \partial(\textrm{Cascade}[\sigma]).

The column x is laid out in memory as a [dynamic] array of computer words  corresponding to row indices, with the natural order of these words being the filtration order.

The persistence algorithm proceeds iteratively, column by column, adding previous columns to the current one. If x is the current column being operated on the next column we will add to it

can be identified as:

y = \textrm{Cascade[Youngest[}\partial(\textrm{Cascade}[\sigma])\textrm{]]]}

Until either the column is zeroed out or a unique pairing occurs, e.g. y = 0.

Now let me restate the definition of y as a procedure:

Step 1) The youngest entry of x is identified.

Step 2) The address of the column y is computed.

Step 3) The address of the column y is fetched into CPU registers.

Usually, this sequence of three steps occurs only after the previous addition completed. Chain addition is generally are implemented as a set_symmetric_difference from begin() to end() on each chain, e.g. oldest entry of each column to the youngest.

In recent versions of both CTL as well as PHAT a change was made to how these column additions  are carried out. The columns are added now added from youngest to oldest elements. This should have the advantage of better locality of reference.

This is because when inspecting the youngest entry we are loading it, along with some amount of the end of the chain into memory. If we then proceeded to add front to back we might end up retiring this cache line in favor of the beginning of the array.

However, adding backwards has even more benefits. Once we add backwards we know that the first pair of elements we inspect will agree, necessarily. However, it is possible,  that the two vectors we add together agree at their tail significantly more. We may delay the allocation of the output buffer for the sum until we find the first mismatch between these two chains. This saves us a small amount of memory. But their is even more.

Supposing that x is not a positive column, e.g. after a call to mismatch we will find a pair of elements in disagreement, precisely the younger of these two elements is the new youngest element.  We may now compute the address of the next column to add to $x$ and request that the computer prefetches the column at that address.

In other words we get some added low level parallelism: as we add the pair of current columns, we are simultaneously fetching the next column to add.

How well does all of this work? In my opinion, quite well. Here is a  plot of the running time for the persistence algorithm showing the original running time, the running time when adding backwards, and the running time when adding backwards with prefetching, on the various datasets from the multicore paper

Feel free to comment and discuss on the results of this experiments. I’ll answer questions the best I can.

Wasserstein barycenters and Frechet means

At this past year at the IMA, there has been some attention spent on a number of interesting aspects in bringing persistent homology closer to statistical methods.

One core step in this process has been to figure out what we mean by an average persistence diagram, a question that has an answer proposed by Munch, Bendich, Turner, Mukherjee, Mattingly, Harer and Mileyko in various constellations.

The details on Frechet means for persistent homology is not what this post is about, however. Instead, I want to bring up something I just saw presented today at ICML. Marco Cuturi and Arnaud Doucet got a paper entitled Fast Computation of Wasserstein Barycenters accepted to this large machine learning conference.

In their paper, Cuturi-Doucet present work on computing the barycenter (or average, or mean) of N probability measures using the Wasserstein distance: they articulate the transport optimization problem of finding a measure minimizing Wasserstein distance to all the N given measures, and present a smoothing approach that allows them to bring the problem onto a convex optimization shape. In the talk — though not present in the paper — the authors argue that they can achieve quadratic running times through these approximation steps. Not only that, but their approach ends up amenable for GPGPU computation and significant parallelization and vectorization benefits.

Their approach works anywhere that the Wasserstein metric is defined, and so in particular should work (and most likely give the same results) on the persistence diagram setting studied by the persistent statistician constellations mentioned above.

I for one would be excited to hear anything about the relations between these (mostly) parallel developments.