J'utilise Ublas :: matrice comprimée pour travailler avec Umfpack, un solveur linéaire rare. Étant donné que je fais une simulation, chaque fois que chaque fois que le système linéaire est construit légèrement différemment, cela pourrait impliquer l'agrandissement / la rétrécissement de la matrice de coefficient et des multiplications de matrice clairsemées. L'échelle du système linéaire est d'environ 25k.
Même s'il y a un patch de reliure pour boost pour travailler avec Umfpack, j'ai toujours besoin de changer la matrice de temps en temps, parfois, même de déterminer le nombre de valeurs non nulles prendrait beaucoup de temps (idéalement, je dois Donnez le nombre de valeurs non nulles lorsque j'initialise une matrice). En outre, j'utilise Ublas :: Gamme pour ajouter des colonnes / rangées de manière dynamique.
Donc, ma question est la suivante: Y a-t-il un moyen efficace de le faire? En ce moment, c'est trop lent pour moi. Transposer une matrice avec une dimension comme 15 000 coûts près de 6 ans et qu'enjout d'environ 12 000 rangées est rapide (parce que je suppose que c'est une matrice majeure de rangée), mais ajoute le même nombre de colonnes à la matrice peut coûter jusqu'à 20 ans (je suppose pour la même chose Raison comme ci-dessus, alors j'ai utilisé une matrice majeure de colonne, le temps total requis serait le même).
Kinda deviendra désespéré ici. Toute suggestion est la bienvenue.
Cheers.
4 Réponses :
Comment construisez-vous la matrice à chaque fois, êtes-vous interface d'une sorte de logiciel différent? Dans ce cas, le temps passé à l'interfaçage est que je suppose est assez faible.
Et vous utilisez -dndebug drapeau, pour Ublas, non?
Je ne suis pas sûr de ce que le problème est ...
meilleur, umut
Bonjour umut, merci de votre attention, je vais le tester plus et essayer de donner une image entière ici.
Je ne suis pas familier avec vos paquets, mais pourquoi est-ce que vous (idéalement) doivent indiquer le nombre d'éléments non nuls dans votre matrice? vous ne pouvez pas surdimensionner puis réduire la taille?
Je suis aussi confus par l'ajout de colonnes pourquoi devraient coûter tant. Un format clairsemé doit être capable de gérer cela. Je conclus que l'une des deux choses se produisent. Soit votre matrice est en cours de conversion en quelque sorte à une matrice non clairsemée avant d'être de retour converti (semble horrible, et impossible dans un paquet de matrice creuse décente) ou le code pour l'insertion est du second degré, car il insère de façon répétée des valeurs, décalage sur toutes les autres chaque temps.
Ce dernier semble probable. Je voudrais essayer de rouler mon propre code « Insérer une colonne » qui prend la matrice clairsemée actuelle, les chiffres combien plus il y a des entrées, Alloue un plus grand bloc, et des copies en séquence, en insérant les nouvelles colonnes que vous allez. Ceci est linéaire, et devrait essentiellement être instantanée. Je ne sais pas si cela est suffisant pour résoudre l'ensemble du problème, mais il devrait être un début.
En outre, si la matrice a l'ordre de 25k entrées, il n'y a pas de réponse raisonnable pourquoi la copie ou la transposition devrait prendre plus de quelques millisecondes. Je pense que vous devez les pièces individuelles de référence de ce problème et déterminer vraiment exactement où le temps va, à moins que la solution ci-dessus pour ajouter les colonnes résout votre problème.
Merci Dov, j'ai été très occupé depuis lors, laissez le problème pendre là-bas pendant un moment. Je vais essayer vos suggestions, pièce par pièce.
Bonjour Dov, pour la transposition, j'ai essayé de transposer une matrice clairsemée majeure de la rangée et de l'attribuer à une matrice ratase majeure à la ligne, il est beaucoup plus lent que si je l'assègre à une matrice de colonne majeure. Je suppose que peut-être que la représentation interne est également modifiée lors de la transposition.
Plutôt que de construire un en joignant plusieurs ensembles de valeurs différents, avez-vous envisagé de les garder dans des matrices distinctes et en utilisant les routines de solveur existantes pour construire votre propre solveur global? Fondamentalement, vous appliqueriez la décomposition appropriée (LU, QR, peu importe) à une matrice de composant, exécutez la mise à jour / la transformation correspondante sur les composants suivants et répétez pour chaque matrice ultérieure. Vous utiliseriez ensuite les matrices de composants factorisés pour calculer votre solution. Il n'est pas clair si la bibliothèque que vous avez travaillé en favoriserait cela directement, ou si vous deviez vous écrir de toutes les routines numériques.
Avez-vous essayé Eigen pour ce genre de problème? Récemment, ils ont terminé la prise en charge des matrices clairsemées.
Depuis que j'ai eu près de 30 vues mais aucune réponse, je pense que ma question n'est peut-être pas très claire. Alors voici quelques détails.
Depuis que je fais la simulation, pour chaque étape de temps, j'ai assembler un système linéaire et résoudre celui-ci qui est fondamentalement juste juste = b. Cependant, la matrice de coefficient A est généralement composée de trois matrices. Une matrice de poids, deux matrices de coefficient pour des contraintes douces et des contraintes difficiles, qui ne peuvent pas être précalisées. (Voir le prochain commentaire)
En raison de la résolution du système linéaire, c'est le résultat de la réduction d'une fonction quadratique au sens le moins carré, je dois faire une multiplication de matrice-matrice pour rendre une matrice T et une multiplication de la matrice-vecteur pour rendre B pour l'intégration de la matrice de contrainte douce le linéaire système. Ensuite, je dois ajouter la matrice de contrainte dure au fond et la droite de T afin de faire A. Enfin, après A et B effectué, je peux les saisir dans Umfpack. (Voir le prochain commentaire)
Comme vous pouvez l'imaginer, il doit y avoir plusieurs opérations impliquant la copie de données, la transposition de matrice et le redimensionnement. Mais je ne sais tout simplement pas comment le rendre plus rapide. Le code est trop long pour être mis ici. Et merci pour votre temps.
Comme il n'y a toujours pas de réponse, quelqu'un peut-il au moins me dire quelle partie de ma question n'est pas assez claire? Tout commentaire est la bienvenue!
La solution classique à ces types de problèmes est de proposer une solution différente ....
Fournir un certain code de démonstration pourrait aider.
Qu'entendez-vous par "Ajout de colonnes"? Cela signifie-t-il que l'ajout d'une nouvelle matrice clairsemée à droite de l'existence?