Numpy "intelligent" de la matrice symétrique

Est-il intelligent et économe en espace symétrique de la matrice dans numpy qui automatiquement et de manière transparente) remplit la position à [j][i] quand [i][j] est écrit?

import numpy
a = numpy.symmetric((3, 3))
a[0][1] = 1
a[1][0] == a[0][1]
# True
print(a)
# [[0 1 0], [1 0 0], [0 0 0]]

assert numpy.all(a == a.T) # for any symmetric matrix

Automatique Hermitian serait bien aussi, bien que je ne vais pas besoin de cela au moment de la rédaction.

Vous pourriez envisager de marquer la réponse acceptée, si cela résout votre problème. 🙂
Je voulais attendre une meilleure (c'est à dire intégré et efficace de la mémoire) réponse à venir. Il n'y a rien de mal avec votre réponse, bien sûr, donc je vais l'accepter de toute façon.

InformationsquelleAutor Debilski | 2010-04-03

70

Si vous pouvez vous permettre de symétriser la matrice juste avant de faire les calculs, les éléments suivants doivent être raisonnablement rapide:
```
def symmetrize(a):
    return a + a.T - numpy.diag(a.diagonal())
```
Cela fonctionne sous des hypothèses raisonnables (par exemple ne pas faire les deux a[0, 1] = 42 et contradictoires a[1, 0] = 123 avant d'exécuter symmetrize).

Si vous avez vraiment besoin d'un transparent symétrisation, vous pourriez envisager de sous-classement numpy.ndarray et simplement redéfinir __setitem__:
```
class SymNDArray(numpy.ndarray):
    def __setitem__(self, (i, j), value):
        super(SymNDArray, self).__setitem__((i, j), value)                    
        super(SymNDArray, self).__setitem__((j, i), value)                    

def symarray(input_array):
    """
    Returns a symmetrized version of the array-like input_array.
    Further assignments to the array are automatically symmetrized.
    """
    return symmetrize(numpy.asarray(input_array)).view(SymNDArray)

# Example:
a = symarray(numpy.zeros((3, 3)))
a[0, 1] = 42
print a  # a[1, 0] == 42 too!
```
(ou l'équivalent avec des matrices au lieu des tableaux, selon vos besoins). Cette approche prend même en charge plus compliqué affectations, comme a[:, 1] = -1, qui définit correctement a[1, :] éléments.

Noter que Python 3 suppression de la possibilité de l'écriture def …(…, (i, j),…), de sorte que le code doit être légèrement adapté avant d'exécuter avec Python 3: def __setitem__(self, indexes, value): (i, j) = indexes...
- En fait, si vous ne sous-classe, vous ne devez pas remplacer setitem, mais plutôt getitem de sorte que vous ne causent pas plus généraux sur la création de la matrice.
- C'est une idée très intéressante, mais à écrire ce que l'équivalent __getitem__(self, (i, j)) échoue lorsque l'on fait un simple print sur une sous-classe de l'instance de array. La raison en est que print appels __getitem__() avec un index entier, de sorte que plus de travail est nécessaire, même pour un simple print. La solution avec __setitem__() fonctionne avec print (évidemment), mais souffre d'un problème similaire: a[0] = [1, 2, 3] ne fonctionne pas, pour la même raison (ce n'est pas une solution parfaite). Un __setitem__() solution a l'avantage d'être plus robuste, depuis le bloc mémoire est correcte. Pas trop mauvais. 🙂
- votre suggestion sonne comme blog.sopticek.net/2016/07/24/...... Ne vous confirmer que c'est presque la même chose ? La difficulté est cela optimise l'utilisation de la mémoire, pas la de temps de calcul. Je suis à la recherche de python méthodes à la vitesse de simples calculs sur des matrices symétriques. s'il vous plaît laissez-moi savoir si vous avez des infos.
- Cette réponse n'a pas d'économiser de la mémoire et est donc très différente de l'approche dans la cité lien. Maintenant, le gain de temps avec des matrices symétriques, il faut généralement aller à travers des algorithmes spécialisés au lieu de général, comme à l'aide de huit() dans NumPy à la place de gie().
InformationsquelleAutor Eric O Lebigot
20

La question plus générale de traitement optimal des matrices symétriques dans numpy m'énerve trop.

Après recherche, je pense que la réponse est probablement que numpy est quelque peu limitée par la disposition de la mémoire supportd par le sous-jacent BLAS routines pour les matrices symétriques.

Alors que certaines routines BLAS faire exploiter la symétrie pour accélérer les calculs sur des matrices symétriques, ils utilisent toujours la même structure de la mémoire comme une matrice, qui est, n^2 l'espace plutôt que de n(n+1)/2. Ils dit que la matrice est symétrique et de n'utiliser que les valeurs soit dans le haut ou le bas du triangle.

Certains scipy.linalg routines de faire accepter les drapeaux (comme sym_pos=True sur linalg.solve) qui sont répercutés sur les routines BLAS, bien que plus de soutien pour de cette dans numpy serait sympa, en particulier des wrappers pour des routines comme DSYRK (symétrique de rang k de mise à jour), ce qui permettrait à un Gramme de la matrice calculé un peu juste plus rapide que la dot(M. T, M).

(Peut sembler pinailleurs à vous soucier de l'optimisation pour un 2x facteur constant sur le temps et/ou dans l'espace, mais il peut faire une différence à ce seuil de quelle taille vous avez un problème vous pouvez gérer sur une seule machine...)
- La question est de savoir sur la façon de créer automatiquement une matrice symétrique à travers l'affectation d'une entrée unique (pas sur la façon BLAS peut être invité à utiliser matrices symétriques dans ses calculs ou comment matrices symétriques pourrait en principe être conservés de manière plus efficace).
- La question se pose également à propos de l'espace-efficacité, de manière BLAS questions sont sur le sujet.
- la question n'est pas sur la façon de créer automatiquement une matrice symétrique à travers l'attribution d'une seule entrée.
- Accordé, "création" pourrait avantageusement être remplacé par "mise à jour". Maintenant, la question est explicitement de manière transparente réglage M_ji quand M_ji est ensemble, et cette réponse n'est pas sur que, vous comprenez que c'est en substance le point que je soulève. La question porte sur la façon la plus efficace de le faire (pas à propos de traiter efficacement les matrices symétriques, même si cela pourrait être la bonne question: quelque chose de mieux mettre sur les commentaires, ou donné comme une réponse qui ne résoudre le problème plus général au lieu de se contenter d'en discuter).
InformationsquelleAutor Matt
7

Il y a un certain nombre de bien-connu des moyens de stockage des matrices symétriques ils n'ont pas besoin d'occuper n^2 éléments de stockage. En outre, il est possible de réécrire les opérations les plus courantes pour accéder à ces révisé le moyen de stockage. L'ouvrage définitif est Golub et Van Loan, Matrice de Calculs, 3ème édition, 1996, Johns Hopkins University Press, articles de 1,27-1.2.9. Par exemple, les citant de la forme (1.2.2), dans une matrice symétrique seulement besoin de stocker A = [a_{i,j} ] pouri >= j. Ensuite, en supposant que le vecteur la tenue de la matrice est notée V, et que A est n-par-n, mettre a_{i,j} dans
```
V[(j-1)n - j(j-1)/2 + i]
```
Cela suppose 1-indexation.

Golub et Van Loan vous proposons un Algorithme 1.2.3 qui vous montre comment accéder à un tel stockées V pour calculer y = V x + y.

Golub et Van Loan également fournir un moyen de stockage d'une matrice à diagonale dominante formulaire. Ce n'est pas de gagner de la place, mais prend en charge l'accès pour certains autres types d'opérations.
- Il est également Rectangulaire Pleine Paniers de stockage (DP), par exemple Lapack ZPPTRF l'utilise. Est-il pris en charge par numpy?
- Non, mais vous pourriez mettre en œuvre un wrapper qui ne
InformationsquelleAutor Jan Galkowski

C'est simple, clair python et pas numpy, mais j'ai juste jeté une routine pour remplir
une matrice symétrique (et un programme de test pour s'assurer qu'il est correct):

import random
# fill a symmetric matrix with costs (i.e. m[x][y] == m[y][x]
# For demonstration purposes, this routine connect each node to all the others
# Since a matrix stores the costs, numbers are used to represent the nodes
# so the row and column indices can represent nodes
def fillCostMatrix(dim):        # square array of arrays
# Create zero matrix
new_square = [[0 for row in range(dim)] for col in range(dim)]
# fill in main diagonal
for v in range(0,dim):
new_square[v][v] = random.randrange(1,10)
# fill upper and lower triangles symmetrically by replicating diagonally
for v in range(1,dim):
iterations = dim - v
x = v
y = 0
while iterations > 0:
new_square[x][y] = new_square[y][x] = random.randrange(1,10)
x += 1
y += 1
iterations -= 1
return new_square
# sanity test
def test_symmetry(square):
dim = len(square[0])
isSymmetric = ''
for x in range(0, dim):
for y in range(0, dim):
if square[x][y] != square[y][x]:
isSymmetric = 'NOT'
print "Matrix is", isSymmetric, "symmetric"
def showSquare(square):
# Print out square matrix
columnHeader = ' '
for i in range(len(square)):
columnHeader += '  ' + str(i)
print columnHeader
i = 0;
for col in square:
print i, col    # print row number and data
i += 1
def myMain(argv):
if len(argv) == 1:
nodeCount = 6
else:
try:
nodeCount = int(argv[1])
except:
print  "argument must be numeric"
quit()
# keep nodeCount <= 9 to keep the cost matrix pretty
costMatrix = fillCostMatrix(nodeCount)
print  "Cost Matrix"
showSquare(costMatrix)
test_symmetry(costMatrix)   # sanity test
if __name__ == "__main__":
import sys
myMain(sys.argv)
# vim:tabstop=8:shiftwidth=4:expandtab

InformationsquelleAutor Davidka

Il est trivial de Pythonically remplir [i][j] si [j][i] est rempli. Le stockage de la question est un peu plus intéressant. On peut compléter le tableau numpy classe avec un packed attribut qui est utile à la fois pour gagner de la place et pour plus tard, lire les données.

class Sym(np.ndarray):
# wrapper class for numpy array for symmetric matrices. New attribute can pack matrix to optimize storage.
# Usage:
# If you have a symmetric matrix A as a shape (n,n) numpy ndarray, Sym(A).packed is a shape (n(n+1)/2,) numpy array 
# that is a packed version of A.  To convert it back, just wrap the flat list in Sym().  Note that Sym(Sym(A).packed)
def __new__(cls, input_array):
obj = np.asarray(input_array).view(cls)
if len(obj.shape) == 1:
l = obj.copy()
p = obj.copy()
m = int((np.sqrt(8 * len(obj) + 1) - 1) / 2)
sqrt_m = np.sqrt(m)
if np.isclose(sqrt_m, np.round(sqrt_m)):
A = np.zeros((m, m))
for i in range(m):
A[i, i:] = l[:(m-i)]
A[i:, i] = l[:(m-i)]
l = l[(m-i):]
obj = np.asarray(A).view(cls)
obj.packed = p
else:
raise ValueError('One dimensional input length must be a triangular number.')
elif len(obj.shape) == 2:
if obj.shape[0] != obj.shape[1]:
raise ValueError('Two dimensional input must be a square matrix.')
packed_out = []
for i in range(obj.shape[0]):
packed_out.append(obj[i, i:])
obj.packed = np.concatenate(packed_out)
else:
raise ValueError('Input array must be 1 or 2 dimensional.')
return obj
def __array_finalize__(self, obj):
if obj is None: return
self.packed = getattr(obj, 'packed', None)

InformationsquelleAutor Charles F

Vous devez vous connecter pour publier un commentaire.