Use Toeplitz-dot-Hankel for very large dimensional transforms

Ouverte
  • Quelque chose ne va pas ?
#209 4 commentaires 0 réactions 0 personnes assignées Voir sur GitHub

Personne n'a encore pris cette issue.

Évaluation

Difficulté
4/5
Temps estimé
3-5 jours
Accessibilité débutants
38/100
Type d'issue
Fonctionnalité
Clarté
Plutôt claire
Activité
À l'abandon
Stack technique
julia
Domaine
performance

Piste de recherche

Commencez par localiser les implémentations des transformations cheb2leg et th_cheb2leg et comparez leur comportement pour les tailles de vecteurs signalées. Faites un benchmark des deux chemins avec n=100, 1 000 et 10 000, puis profilez le cas matriciel et les FFTs mentionnées dans l’issue. Le travail est terminé lorsque le chemin le plus rapide est choisi pour les très grands tableaux sans réintroduire les régressions signalées ni des allocations excessives.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

Toeplitz-dot-Hankel has better complexity plans so should be the default when arrays are large: Eg for cheb2leg even n = 1000 sees a signifcant speedup:

julia> n = 100; x = randn(n); @time cheb2leg(x); @time th_cheb2leg(x);
  0.000267 seconds (2 allocations: 944 bytes)
  0.000654 seconds (98 allocations: 288.531 KiB)

julia> n = 1000; x = randn(n); @time cheb2leg(x); @time th_cheb2leg(x);
  0.028686 seconds (2 allocations: 7.984 KiB)
  0.006464 seconds (99 allocations: 10.559 MiB)

julia> n = 1000; x = randn(n); @time cheb2leg(x); @time th_cheb2leg(x);
  0.028856 seconds (2 allocations: 7.984 KiB)
  0.011597 seconds (99 allocations: 10.559 MiB)

julia> n = 10_000; x = randn(n); @time cheb2leg(x); @time th_cheb2leg(x);
  0.778423 seconds (3 allocations: 78.219 KiB)
  0.103821 seconds (108 allocations: 799.524 MiB)

This was prematurely changed but reverted as there were some regressions. But also the number of allocations in th_* is exorbitant, probably because it dates back to a port of Matlab code.

For matrices I'm not seeing much improvement in the th_*, even for a 40k x 10 transform, which is suspicious....but doing a profile all the time is in the FFTs

Langage dominant
Julia
Étoiles
284
Forks
28
Merge moyen
9 h 21 min
PR mergées (30 j)
2

Préparer son environnement

Ce projet ne fournit ni conteneur de développement, ni Dockerfile, ni guide de contribution : l'installation est à votre charge. Commencez par son README, et consultez notre guide de la première contribution pour les étapes générales.

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de JuliaApproximation/FastTransforms.jl

Toutes les issues de JuliaApproximation/FastTransforms.jl

Issues similaires

Plus d'issues Julia

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.