Обсуждение:Умножение матриц

Предмет статьиПравить

А мне кажется немного странным смешение в одной статьи чисто математического аспекта и вычислительного. Я бы разделил эту статьи на две. --OZH 19:11, 13 октября 2010 (UTC)Ответить[ответить]

Для двух статей по-моему у нас мало материала. А "примеры реализации" надо бы перенести в викиучебник. -- X7q 19:25, 13 октября 2010 (UTC)Ответить[ответить]

У нас — да, а вообщее — полно. ;-) --OZH 05:15, 14 октября 2010 (UTC)Ответить[ответить]

ОТ вашей статьи пользы, как от козла молока.84.51.99.130 15:28, 25 декабря 2011 (UTC)Ответить[ответить]

Прямое умножениеПравить

Кроме описанного в статье, известно так же прямое умножение, которое состоит в следующем. Каждый элемент матрицы-ответа равен произведению двух соответствующих элементов матриц-множителей (т.е. аналогично сложению матриц). При записи обычно используется черта сверху, чтобы отличить прямое умножение от обычного. Жабыш 16:33, 22 апреля 2011 (UTC)(Жабыш)Ответить[ответить]

Блочное и буферизованное умножение, векторизация (SSE/AVX) и пр.Править

В статье до этой правки участника Vlsergey-at-work была информация о том, что при программной реализации операции умножения матриц применяется ряд приемов, таких как блочное или буферизованное умножение, векторизация и пр. со ссылками на мои работы и не только (каюсь, грешен, действительно этим занимаюсь, однако не один я, ссылки были и на другие работы). Указанным участником вся эта информация была удалена, несмотря на то, что данные подходы существенно поднимают эффективность работы подсистемы памяти и активно применяются на практике. На наличии ссылок на мои работы не настаиваю, но наличие информации об алгоритмах умножения предлагаю вернуть обратно. Поэтому предлагаю следующее 1. Правку вышеуказанного участника убираем, возвращаем текст как было до нее. 2. Текст возвращаем, ссылки на меня убираем. 3. Оставляем как есть, я к статье больше не прикасаюсь, ее пишут другие. Ваше мнение?

PS. В статье ни слова не сказано про то, как, например, умножение матриц реализуется на систолических структурах или матричных мультипроцессорах, я планирую этот кусок дописать (там вообще получается линейное время!). Стоит этим заниматься или его постигнет та же участь под предлогом того, что по этой тематике есть патенты с моим участием? Evatutin 13:11, 9 февраля 2016 (UTC)Ответить[ответить]

• Раздел был про «Алгоритмы быстрого перемножения матриц», некоторые уже успели стать «классическими», уменьшающие асимптотическую сложность алгоритмов. Приёмы же с локальными оптимизациями программной реализации нужно (если вообще нужно) описывать в отдельном разделе, и, очевидно, не по своим источнкам. — VlSergey ^(трёп) 13:18, 9 февраля 2016 (UTC)Ответить[ответить]
  • Если вы обратили внимание, в источниках была книга Борескова и Харламова, к авторству которой я никакого отношения не имею, в ней описание указанных приемов есть. Кто впервые предложил буферизовать j-й столбец и применять блочное умножение, я сказать затрудняюсь. В моих статьях эти подходы были опробованы на современном железе, приведено описание ряда особенностей, о чем в вики как правило не пишут. CUDA альманах, выпускаемый под эгидой NVidia, на ваш взгляд тоже является неавторитетным, как и наши Известия? Описание буферизованного умножения есть в Software optimization manual от Intel, при необходимости ссылку можно поискать и привести. Evatutin
    • Потому и не пишут, что сегодня одно железо с одними приёмами, завтра другое -- с другими. Нет, CUDA-альманах от NVidia не является вторичным авторитетным источником по вопросу, какие оптимизации использовать в архитектуре CUDA. То есть про сами-то оптимизации они авторитетны, но вот по вопросу, насколько эти CUDA-оптимизации важны для понимания вопроса умножения матриц -- нет. -- VlSergey ^(трёп) 13:54, 9 февраля 2016 (UTC)Ответить[ответить]
      • CUDA-реализация (как и другие GPU-ориентированные реализации) являются одними из самых быстрых, если мы говорим об 1 машине, а не о кластере или суперкомпьютере, не упомянуть о них в статье было бы на мой взгляд странно, тем более в разделе об алгоритмах. Базируются данные реализации на алгоритмах, которые были разработаны задолго до появления CUDA'ы и K, а вы предлагаете об этом умолчать, в данном вопросе я с вами не соглашусь. В тексте английской статьи есть упоминание об алгоритме, который экономит пересылки данных между узлами и эффективен на кластерах (см. разделы Parallel matrix multiplication и Communication-avoiding and distributed algorithms) — давайте и их уберем за компанию? Или лучше переведем и добавим в русскую статью? Evatutin 14:14, 9 февраля 2016 (UTC)Ответить[ответить]
        • ВП:ЕСТЬДРУГИЕСТАТЬИ. Сейчас в рамках этой статьи в разделе «алгоритмы» приведены такие, которые описывают решение абстрагируясь от типа вычислителя. Было выше предложено написать отдельный раздел про оптимизацию под отдельные типы процессоров. Этот вариант устроит или нет? — VlSergey ^(трёп) 16:05, 9 февраля 2016 (UTC)Ответить[ответить]
          • Давайте сделаем отдельный раздел или 2 подраздела в алгоритмах (вроде универсальных и ориентированных на что-то), я не возражаю. Если вы не возражаете, предлагаю сделать это вам в том виде, в котором вы считаете нужным. Готов дополнить их по сравнению с тем, что было до удаления. Я искренне рад, что мы пришли к взаимопониманию! Evatutin 16:55, 9 февраля 2016 (UTC)Ответить[ответить]

• P.S.: если там получится линейное время, не забудьте ссылку на надёжные авторитетные источники (не на статьи в трудах ВУЗов). Потому что необычные утверждения требуют надёжных источников. — VlSergey ^(трёп) 13:20, 9 февраля 2016 (UTC)Ответить[ответить]
  • Посмотрите книгу Куна "Матричные мультипроцессоры на СБИС" и, например, А.с. СССР № 1534471 — время умножения пары квадратных матриц на систолической структуре из N*N ячеек составляет 6*N тактов, если мне не изменяет память Evatutin 13:35, 9 февраля 2016 (UTC)Ответить[ответить]
    • Угу, угу. Если взять N^2 вычислителей то за линейное время мы, конечно, матрицы перемножим. Но к алгоритмам, выполняющимся за линейное время, это отношение не имеет. -- VlSergey ^(трёп) 13:52, 9 февраля 2016 (UTC)Ответить[ответить]
      • Асимптотическая временная сложность алгоритма, ориентированного на подобную специализированную вычислительную структуру, как раз O(N). Способов более быстрого умножения матриц на практике (алгоритм все таки во многом вещь абстрактная без программной или аппаратной реализации) мне неизвестно. Давайте подведем итог (что предлагаете вы из 3 пунктов, которые в самом первом посте обозначил я?) и выслушаем мнение других участников. Evatutin 14:14, 9 февраля 2016 (UTC)Ответить[ответить]
        • Слушайте, ну давайте возьмём специализированную вычислительную структуру с N³ вычислителями и получим константную временную сложность. Что это докажет и зачем это нужно в статье? — VlSergey ^(трёп) 16:09, 9 февраля 2016 (UTC)Ответить[ответить]
          • У меня есть определенные сомнения, что это возможно реализовать эффективно, но вы можете попробовать при желании :) Evatutin 16:55, 9 февраля 2016 (UTC)Ответить[ответить]

Use this if you want toПравить

Translated using Google: Это даст вам мышечную память о том, как умножать матрицы. Так как левая рука представляет собой строки, это также поможет вам вспомнить, что левый индекс относится к ряду, а правый индекс относится к колонке--Guy vandegrift (обс.) 16:19, 10 февраля 2017 (UTC)Ответить[ответить]

 

This will give you muscle memory on how to multiply matrices. Since the left hand represents rows, it also helps you remember that the left index refers to row, while the right index refers to column.