L'algèbre linéaire traite des espaces vectoriels et des transformations linéaires.
En réponse à une question précédente , j'ai mentionné la croyance commune mais fausse selon laquelle l' élimination «gaussienne» se fait dans le temps O(n3)O(n3)O(n^3) . Bien qu'il soit évident que l'algorithme utilise des opérations arithmétiques O(n3)O(n3)O(n^3) , une mise en œuvre négligente...
Il est largement supposé que , l'exposant optimal pour la multiplication matricielle, est en fait égal à 2. Ma question est simple:ωω\omega Quelles raisons avons-nous pour croire que ?ω=2ω=2\omega = 2 Je connais des algorithmes rapides comme Coppersmith-Winograd, mais je ne sais pas pourquoi ils...
Ma question est simple: Quel est le temps d'exécution le plus défavorable du meilleur algorithme connu pour calculer une composition simple d'une matrice ?n × nn×nn \times n Eigendecomposition réduit-il à la multiplication matricielle ou les algorithmes les plus connus (via SVD ) sont-ils dans le...
Il est communément admis que pour tout , il est possible de multiplier deux matrices en un temps . Une discussion est ici .ϵ>0ϵ>0\epsilon > 0n×nn×nn \times nO(n2+ϵ)O(n2+ϵ)O(n^{2 + \epsilon}) J'ai demandé à des personnes plus familières avec les recherches si elles pensaient qu'il y avait un...
Je voudrais trouver un algorithme de temps polynomial qui détermine si la durée d'un ensemble donné de matrices contient une matrice de permutation. Si quelqu'un sait si ce problème est d'une classe de complexité différente, ce serait tout aussi utile. EDIT: J'ai étiqueté cette question avec la...
Étant donné une matrice binaire par (les entrées sont ou 1 ), le problème est de déterminer s'il existe deux vecteurs binaires v 1 ≠ v 2 tels que M v 1 = M v 2 (toutes les opérations effectuées sur Z ). Ce problème est-il difficile à NP?n M 0mmmnnnMMM000111v1≠v2v1≠v2v_1 \ne v_2Mv1=Mv2Mv1=Mv2Mv_1 =...
Soit une matrice entière carrée, et soit un entier positif. Je m'intéresse à la complexité du problème de décision suivant:MMMnnn L'entrée en haut à droite de positive?MnMnM^n Notez que l'approche évidente du quadrillage itéré (ou de tout autre calcul explicite) nous oblige à gérer potentiellement...
Je recherche une bonne enquête sur les algorithmes et la complexité de l'algèbre linéaire (opérations comme le rang, l'inverse, les valeurs propres, ... pour les matrices booléennes, et entières / rationnelles) en mettant l'accent sur les algorithmes parallèles ( hiérarchie N C ) et polytemporels ....
Une propriété de base des espaces vectoriels est qu'un espace vectoriel V⊆Fn2V⊆F2nV \subseteq \mathbb{F}_2^n de dimension n−dn−dn-d peut être caractérisé par ddd contraintes linéaires linéairement indépendantes - c'est-à-dire qu'il existe ddd vecteurs linéairement indépendants...
Je recherche un document d'enquête ou un livre couvrant les résultats sur la complexité spatiale des opérations d'algèbre linéaire courantes telles que le classement matriciel, le calcul des valeurs propres, etc. est plus facile de tracer les résultats temporels. J'apprécie toute référence en la...
Je m'intéresse au problème suivant: étant donné les matrices entières décident si chaque produit infini de ces matrices est finalement égal à la matrice zéro.A1,A2,…,AkA1,A2,…,AkA_1,A_2, \ldots, A_k Cela signifie exactement ce que vous pensez qu'il fait: nous dirons que l'ensemble des matrices a la...
Une matrice est dite totalement régulière si toutes ses sous-matrices carrées ont un rang complet. De telles matrices ont été utilisées pour construire des superconcentrateurs. Quelle est la complexité de décider si une matrice donnée est totalement régulière sur les logiques? Sur des champs finis?...
Je suis intéressé par la complexité de la résolution d'équations linéaires modulo k , pour k arbitraire (et avec un intérêt particulier pour les puissances premières), en particulier: Problème. Pour un système donné de équations linéaires dans n modules inconnus k , existe-t-il des...
Considérez équipé du produit scalaire standard et vecteurs: . Nous voulons construire une structure de données qui autorise les requêtes au format suivant: étant donné output . Est-il possible d'aller au-delà du temps de requête O (nm) trivial ? Par exemple, si n = 2 , alors il est immédiat...
En 1979, Freivalds a montré que la vérification des produits matriciels sur n'importe quel champ peut être effectuée en temps randomisé . Plus formellement, étant donné trois matrices A, B et C, avec des entrées d'un champ F, le problème de vérifier si AB = C a un algorithme de temps randomisé .O (...
Quels sont les algorithmes efficaces connus pour calculer un déterminant d'une matrice entière à coefficients dans , l'anneau de résidus modulo . Le nombre peut ne pas être premier mais composite (donc les calculs sont effectués en anneau, pas dans un champ). mmZmZm\mathbb{Z}_mmmmmmm Pour autant...
Est-il possible de tester algorithmiquement si un nombre calculable est rationnel ou entier? En d'autres termes, serait-il possible pour une bibliothèque qui implémente des nombres calculables de fournir les fonctions isIntegerou isRational? Je suppose que ce n'est pas possible, et que cela est en...
Je suis intéressé par une fonction booléenne explicite avec la propriété suivante: si est constant sur un sous-espace affine de , alors la dimension de ce sous-espace est .f:0,1n→0,1f:0,1n→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}fff0,1n0,1n\\{0,1\\}^no(n)o(n)o(n) Il n'est pas difficile de...
Dans l'algorithme de Strassen, pour calculer le produit de deux matrices et , les matrices et sont divisées en matrices de blocs et l'algorithme procède calcul récursif de produits matrice-matrice à blocs par opposition à un produit matriciel matriciel à blocs, c'est-à-dire si nous voulons , où B A...
Étant donné deux matrices A et B , le problème de décider s'il existe une matrice de permutation P telle que B = P - 1 A P est équivalent à (Isomorphisme graphique). Mais si nous relaxons P pour n'être qu'une matrice inversible, alors quelle est la complexité? Existe-t-il d'autres restrictions sur...