Hay varios factores que contribuyen a la mejora del rendimiento del algoritmo se menciona en el documento; el uso de cohomology es uno, pero también hay un computacional de acceso directo de los involucrados, y la parte superior Betti número (más precisamente, el dth Betti número de la (d+1)-esqueleto) también juega un papel.
El cálculo de la persistencia de los códigos de barras se basa en una variante de la eliminación Gaussiana, aplica a las columnas de los límites de la matriz de filtrado de la cadena de complejos. Desde la filtración de orden es importante, no hay columnas se intercambian, y las eliminaciones se realiza sólo mediante la izquierda-a-derecha de la columna de adiciones. Eliminación gaussiana no hacer uso del hecho de que la matriz es un límite de la matriz. Pero este hecho puede ser aprovechado para tomar un importante acceso directo en la reducción de la matriz.
Este acceso directo, llamado el "clearing" de optimización, permite borrar todas las columnas a la vez. El acceso directo se ha encontrado de forma independiente por Chao y Kerber así como por Morozov et al. (su uso está implícito en la descripción de la cohomology algoritmo del citado documento). De compensación se aplica tanto a la homológica y cohomological versiones de código de barras de la computación. En el mencionado documento, la cohomology aplicaciones del algoritmo de compensación, mientras que la homología algoritmo no.
Los resultados experimentales del papel así nos dicen que la persistencia de la cohomology con la limpieza es más rápida que la homología persistente sin compensación. Como resulta, sin embargo, cohomology con la limpieza también es más rápido que homología con la limpieza en los ejemplos típicos, aclarar el papel de las cohomology de cálculo a los efectos de.
La aplicación de compensación requiere la ejecución de las operaciones de columna en el orden apropiado. Por homología, limpieza de la columna de un q-simplex requiere la reducción de la columna de a (q+1)-simplex primera. En cohomology, en contraste, la desactivación de la columna de un q-simplex requiere la reducción de la columna de a (q-1)-simplex primera.
Si el objetivo es calcular la persistencia de los códigos de barras sólo hasta un cierto homológica de grado d, el cómputo se inicia con la reducción de las columnas de (d+1)-simplices. Para las columnas, intercambio de información no es disponible. El número de columnas que va a ser reducido a cero la columna es exactamente la
(d+1)st Betti número de la (d+1)-esqueleto.
Especialmente ahora, cuando la informática persistencia de Vietoris–Rip filtraciones, el grado d es elegido normalmente pequeño, y hay un montón más (d+1)-simplices de simplices de menor dimensión, y también el (d+1)st Betti número será grande. En el cómputo de homología persistente, limpieza de sólo ceros columnas de menores dimensiones simplices, y por lo que el speedup obtenido puede ser muy pequeña. Por otro lado, para cohomology, compensación está disponible sólo para 0-simplices, pero el número de 0-simplices es pequeña, y la persistencia en la dimensión 0 se puede calcular rápidamente mediante una unión-hallar la estructura de datos en su lugar.
En resumen: la limpieza acelera el cálculo de la persistencia, y cohomology permite por lo general más que aclarar que la homología, especialmente en el caso de Vietoris–Rip filtraciones.
