| rdfs:comment
| - Coppersmithův–Winogradův algoritmus, pojmenovaný po a , je asymptoticky nejrychlejší známý algoritmus pro násobení matic. Lze s ním vynásobit dvě matice v čase . Jde o zlepšení oproti u triviálního algoritmu a u Strassenova algoritmu. Mohlo by být možné exponent dále zlepšit, nicméně exponent musí být alespoň 2 (protože matice má hodnot a každou z nich je nutné alespoň jednou přečíst, aby bylo možné spočítat přesný výsledek). (cs)
- En lineara algebro, la algoritmo de Coppersmith-Winograd estas asimptote la plej rapida sciata algoritmo por matrica multipliko de kvadrataj matricoj (kiel en 2008). La algoritmo estas nomita post kaj . Ĝi povas multipliki du n×n matricojn en tempodaŭro O(n2,376). Ĉi tio estas plibonigo super la bagatela O(n3) de norma algoritmo kaj la O(n2,807) de algoritmo de Strassen. La norma matrica multiplika algoritmo uzas senperan kalkulon laŭ difino de matrica multipliko cik = Σaijbjk (eo)
- L’algorithme de Coppersmith-Winograd est un algorithme de calcul du produit de deux matrices carrées de taille dû à Don Coppersmith et Shmuel Winograd en 1987. Sa complexité algorithmique est en ce qui en fait l'algorithme actuel le plus efficace asymptotiquement. Rien n'indique que la complexité est optimale, l'exposant 2 étant généralement considéré comme optimal. L'algorithme de Coppersmith-Winograd a été retrouvé par des méthodes de représentation des groupes finis. (fr)
- Em álgebra linear, o algoritmo de Coppersmith–Winograd é um algoritmo de multiplicação de matrizes quadradas que, apresenta a maior velocidade assimptótica conhecida até o ano de 2008. O algoritmo recebe o nome de Don Coppersmith e Shmuel Winograd e é capaz de multiplicar matrizes quadradas de dimensão n num tempo de (ver notação Grande-O), tendo então desempenho superior quando comparado com o algoritmo trivial, que corre num tempo , e com o algoritmo de Strassen, de tempo . Pode ser viável melhorar ainda mais o expoente, no entanto ele deve ser pelo menos 2 (uma vez que uma matriz tem valores que precisam ser lidos ao menos uma vez para calcular o resultado exato). (pt)
- Алгоритм Копперсміта — Вінограда (англ. Coppersmith–Winograd algorithm) — алгоритм для швидкого множення матриць. Алгоритм використовує ідеї, схожі з алгоритмом Штрассена. До 2010 року, алгоритм Копперсміта-Винограда був найбільш асимптотично швидким. Алгоритм названо на честь його розробників Дона Копперсміта і Шмуеля Вінограда. (uk)
- Алгоритм Копперсмита—Винограда — алгоритм умножения квадратных матриц, предложенный в 1987 году Д. Копперсмитом и . В исходной версии асимптотическая сложность алгоритма составляла , где — размер стороны матрицы. Алгоритм Копперсмита—Винограда, с учетом серии улучшений и доработок в последующие годы, обладает лучшей асимптотикой среди известных алгоритмов умножения матриц. (ru)
|
| has abstract
| - Coppersmithův–Winogradův algoritmus, pojmenovaný po a , je asymptoticky nejrychlejší známý algoritmus pro násobení matic. Lze s ním vynásobit dvě matice v čase . Jde o zlepšení oproti u triviálního algoritmu a u Strassenova algoritmu. Mohlo by být možné exponent dále zlepšit, nicméně exponent musí být alespoň 2 (protože matice má hodnot a každou z nich je nutné alespoň jednou přečíst, aby bylo možné spočítat přesný výsledek). Coppersmithův–Winogradův algoritmus se často používá jako stavební prvek v jiných algoritmech k dokázání jejich teoretické časové náročnosti. Nicméně na rozdíl od Strassenova algoritmu se příliš nepoužívá v praxi, protože je výhodnější až pro matice velmi velkých řádů. (cs)
- En lineara algebro, la algoritmo de Coppersmith-Winograd estas asimptote la plej rapida sciata algoritmo por matrica multipliko de kvadrataj matricoj (kiel en 2008). La algoritmo estas nomita post kaj . Ĝi povas multipliki du n×n matricojn en tempodaŭro O(n2,376). Ĉi tio estas plibonigo super la bagatela O(n3) de norma algoritmo kaj la O(n2,807) de algoritmo de Strassen. La norma matrica multiplika algoritmo uzas senperan kalkulon laŭ difino de matrica multipliko cik = Σaijbjk Eble eblas plibonigi la eksponenton super la matrica amplekso n plu. Tamen, la eksponento devas esti minimume 2 ĉar n×n matrico enhavas n2 valorojn, kaj ili ĉiuj devas esti legitaj dum kalkulado por ricevi la akuratan rezulton. La algoritmo de Coppersmith-Winograd estas ofte uzata kiel parto en aliaj algoritmoj por pruvi teoriajn tempajn komplikecajn barojn. Tamen, malsimile la algoritmo de Strassen, ĝi ne estas uzata en praktiko ĉar ĝi donas avantaĝon nur por matricoj tiel grandaj ke ilin ne povas prilabori moderna aparataro. Henry Cohn, Robert Kleinberg, Balázs Szegedy kaj Christopher Umans rederivis la algoritmon de Coppersmith-Winograd per grupo-teoria konstruado. Ili ankaŭ montris ke ĉiu el du malsamaj konjektoj implicas ke la eksponento por tempodaŭro de matrica multipliko estas 2, kiel estas longe suspektite. (eo)
- L’algorithme de Coppersmith-Winograd est un algorithme de calcul du produit de deux matrices carrées de taille dû à Don Coppersmith et Shmuel Winograd en 1987. Sa complexité algorithmique est en ce qui en fait l'algorithme actuel le plus efficace asymptotiquement. Rien n'indique que la complexité est optimale, l'exposant 2 étant généralement considéré comme optimal. L'algorithme est utilisé comme brique de base pour prouver des résultats théoriques sur la complexité algorithmique. Mais aucune implémentation de l'algorithme n'est utilisée car la constante dans le grand O est prohibitive (il est moins performant que celui de Strassen sur toute matrice qui tiendrait dans la mémoire d’un ordinateur actuel). L'algorithme de Coppersmith-Winograd a été retrouvé par des méthodes de représentation des groupes finis. Dans sa thèse, Andrew Stothers améliore la borne sur la complexité de l'algorithme, montrant qu'elle est inférieure à 2,3737. (fr)
- Em álgebra linear, o algoritmo de Coppersmith–Winograd é um algoritmo de multiplicação de matrizes quadradas que, apresenta a maior velocidade assimptótica conhecida até o ano de 2008. O algoritmo recebe o nome de Don Coppersmith e Shmuel Winograd e é capaz de multiplicar matrizes quadradas de dimensão n num tempo de (ver notação Grande-O), tendo então desempenho superior quando comparado com o algoritmo trivial, que corre num tempo , e com o algoritmo de Strassen, de tempo . Pode ser viável melhorar ainda mais o expoente, no entanto ele deve ser pelo menos 2 (uma vez que uma matriz tem valores que precisam ser lidos ao menos uma vez para calcular o resultado exato). O algoritmo de Coppersmith–Winograd é usado frequentemente como base para a construção de outros algoritmos para provar cotas teóricas sobre tempo de processamento. Porém, ao contrário do algoritmo de Strassen, ele não é usado na prática porque só é vantajoso para matrizes tão grandes que não podem ser processadas pelo hardware existente atualmente. Henry Cohn, , Balázs Szegedy e obtiveram novamente o algoritmo de Coppersmith–Winograd usando uma construção da teoria de grupos. Eles também mostraram que qualquer uma de duas conjecturas diferentes implicariam que o expoente ótimo para a multiplicação de matrizes é 2, como se suspeita há muito tempo. (pt)
- Алгоритм Копперсмита—Винограда — алгоритм умножения квадратных матриц, предложенный в 1987 году Д. Копперсмитом и . В исходной версии асимптотическая сложность алгоритма составляла , где — размер стороны матрицы. Алгоритм Копперсмита—Винограда, с учетом серии улучшений и доработок в последующие годы, обладает лучшей асимптотикой среди известных алгоритмов умножения матриц. На практике алгоритм Копперсмита—Винограда не используется, так как он имеет очень большую константу пропорциональности и начинает выигрывать в быстродействии у других известных алгоритмов только для матриц, размер которых превышает память современных компьютеров. (ru)
- Алгоритм Копперсміта — Вінограда (англ. Coppersmith–Winograd algorithm) — алгоритм для швидкого множення матриць. Алгоритм використовує ідеї, схожі з алгоритмом Штрассена. До 2010 року, алгоритм Копперсміта-Винограда був найбільш асимптотично швидким. Алгоритм названо на честь його розробників Дона Копперсміта і Шмуеля Вінограда. Використовуючи цей алгоритм можна помножити дві матриці за одиниць часу. Такий результат є кращим за наївний алгоритм та алгоритм Штрассена. Алгоритми зі швидшим асимптотичним часом роботи, ніж алгоритм Штрассена рідко використовується на практиці, оскільки їхні великі сталі числа, у швидкості їх обрахунків, роблять їх непрактичними. Показник можна ще покращити, однак, показник не може бути меншим за 2 (бо матриця має значення і кожне з них повинне бути прочитане принаймні раз для обчислення точного результату). У 2010 Ендрю Стосерс запропонував покращення алгоритму з асимптотичним часом . У 2011 Вірджинія Вільямс скомбінувала виверт зі Стосерсової статті зі своїми ідеями і автоматизованою комп'ютерною оптимізацією пропонуючи асимптотично швидший алгоритм. У 2014 році Франсуа Ле Ґалл спростив метод Вільямс і отримав краще асимптотичне наближення . Алгоритм Копперсміта — Вінограда часто використовується як основа для інших алгоритмів, щоб довести теоретичні межі швидкості обрахунків. Проте, на відміну від алгоритму Штрассена, він не використовується на практиці, оскільки він забезпечує перевагу лише для матриць настільки великих, що вони не можуть бути оброблені сучасним обладнанням. Генрі Кон, Роберт Клейнберг, Балаж Щеґеди і Кріс Уманс повторно вивели алгоритм Копперсміта — Вінограда, використовуючи теоретико-груповий підхід. Вони також показали, що кожен з двох підходів передбачає, що оптимальним показником для алгоритму множення матриць є 2, як давно підозрювали у наукових колах. Тим не менш, вони не змогли сформулювати конкретний розв'язок, що привів би до кращого часу обчислення, ніж алгоритм Копперсміта — Вінограда. (uk)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)