Какие работы производятся с матрицей лд
Перейти к содержимому

Какие работы производятся с матрицей лд

  • автор:

Матрица ADL/LD

Модель “ADL/LC” (Arthur D. Little / Life Cicle) является одной из наиболее распространенных моделей, использующих понятие жизненного цикла бизнес-единицы или отрасли. Здесь предполагается, что любой бизнес последовательно проходит в своем существовании этапы рождения, развития, зрелости и спада. Анализ позиции конкретного бизнеса проводится в координатных осях “стадия жизненного цикла продукта — относительное положение на рынке (конкурентная позиция бизнеса)”. Согласно модели, относительное положение бизнеса на рынке может быть ведущим, сильным, заметным, прочным, слабым. Таким образом, получается матрица 4х5 (рис. 5). Процедура выбора стратегических решений складывается из трех шагов. На первом шаге стратегия предварительно и в общей форме определяется в соответствии с тем, какую клетку матрицы занимает данный конкретный бизнес. На втором шаге учитывается позиционирование бизнеса внутри данной клетки матрицы. В зависимости от позиции здесь осуществляется выбор линий дальнейшего движения бизнеса и конкретизация стратегий, хотя формулировки стратегий здесь также носят еще достаточно общий характер. Для каждой из ячеек матрицы существуют свои возможные стратегические маршруты по линии естественного развития или линии избирательного развития (рис. 5), и, соответственно выбору, свой набор уточненных стратегий. Поэтому на третьем шаге осуществляется выбор уточненной стратегии, соответствующей выбранному пути развития бизнеса. Здесь для каждой из возможных ситуаций предлагается конкретный набор комбинаций из 24 уточненных стратегий, причем последние формулируются в терминах хозяйственных операций.

clip_image002

Рисунок 5. Матрица модели ADL/LC

Сильные стороны, характеризующие относительное положение бизнеса на рынке, могут определять такие переменные, как: степень патентной защищенности; эффективность производства; степень вертикальной интеграции; отношение менеджмента к возможным рискам, и др.

Как и в случае матрицы Мак-Кинзи, получение интегральной оценки базируется на использовании весовых коэффициентов и экспертных данных. Выбор конкретных параметров (их число может достигать 10) может быть продиктован конкретной ситуацией, при этом методика расчетов аналогична матрице Мак-Кинзи.

В рамках модели ADL-LC возможно проведение не только статического, но и динамического анализа, а также прогнозирования как в краткосрочной, так и в долгосрочной перспективе.

Модуль светодиодной матрицы

Модуль светодиодной матрицы

Основные сведения Модуль светодиодной матрицы предназначен для отображения символьной и графической информации. В основе модуля лежит светодиодная матрица из 64 красных 3 мм светодиодов. В зависисмости от того какое количество светодиодов и в какой последовательности загорается — можно вывести практически любую информацию: от простейших символов, букв и цифр, до более сложных графических элементов, в том числе динамических. Особенностью светодиодных матриц, в отличие от дисплеев, является низкий уровень энергопотребления (максимально 70 мА при одновременном использовании всех светодиодов). Для управления матрицей используется микросхема MAX7219. С ее помощью для управления 64 светодиодами потребуется всего три цифровых вывода контроллера. Кроме того модули можно объединять друг с другом используя все те же 3 вывода контроллера. Объединив несколько модулей — можно получить светодиодную панель или бегущую строку практически любых размеров. Для удобства крепления на плате предусмотрены 4 монтажных отверстия под винты М3. Технические характеристики — рабочее напряжение: 3,3-5 В — максимальный потребляемый ток: 70 мА — размер матрицы: 32х32 мм — диаметр светодиода: 3 мм — габаритные размеры ДхШхВ: 46х33х9 мм Страна производства: Россия Гарантия: 12 месяцев Подключение Модуль индикатора подключается к контроллеру с помощью следующих выводов: + — соединяется с пином питания контроллера (5V или 3,3V) — соединяется с пином контроллера GND (земля) CLK — соединяется с цифровым пином контроллера LD — соединяется с цифровым пином контроллера DIN — соединяется с цифровым пином контроллера DO — предназначен для соединения нескольких модулей друг с другом и подключаетсяя к выводу DIN следующего модуля Комплектация — модуль светодиодной матрицы х1 — пакет упаковочный х1 Ссылки «База знаний» — Модуль светодиодной матрицы Библиотека для работы с модулем

Сопутствующие товары

Набор проводов 20 шт, 20 см,

Набор проводов 20 шт, 20 см, «папа — мама» Набор из 20 проводов «папа-мама» длиной 20 см

Набор проводов 20 шт, 20 см,

Набор проводов 20 шт, 20 см, «мама — мама» Набор из 20 проводов «мама-мама» длиной 20 см

Комплект винтов и гаек М3

Комплект винтов и гаек М3 Комплект металлических винтов и гаек М3 для монтажа модулей и датчиков

Комплект нейлоновых креплений

Комплект нейлоновых креплений Комплект из нейлоновых креплений для монтажа модулей и датчиков

Метод Холецкого (нахождение симметричного треугольного разложения)

1 Разложение Холецкого (метод квадратного корня), базовый точечный вещественный вариант для плотной симметричной положительно определённой матрицы

1.1 [math]LL^T[/math] -разложение

Разложение Холецкого — представление симметричной положительно определённой матрицы [math]A=A^T\gt 0[/math] в виде произведения [math]A = LL^T[/math] , где [math]L[/math] — нижняя (Lower) треугольная матрица со строго положительными элементами на диагонали. Иногда разложение удобно записать в эквивалентной форме [math]A = U^TU[/math] , где [math]U = L^T[/math] — верхняя (Upper) треугольная матрица. Для любой симметричной положительно определённой матрицы разложение Холецкого существует и единственно.

Элементы матрицы [math]L[/math] можно вычислить, начиная с верхнего левого угла матрицы [math]A[/math] , по формулам:

Выражение под квадратным корнем всегда положительно, если [math]A[/math] — вещественная симметричная положительно определённая матрица.

Вычисление происходит сверху вниз, слева направо, т.е. сначала вычисляется [math]L_[/math] ( [math]j \lt i[/math] ), а уже затем [math]L_[/math] . Вычисления обычно проводятся в одной из следующих последовательностей.

  • Алгоритм Холецкого-Банашевича (Cholesky–Banachiewicz algorithm) или просто алгоритм Холецкого, когда вычисления начинаются с верхнего левого угла матрицы [math]L[/math] и проводятся по строкам. Этот вариант разложения используется наиболее часто, особенно при использовании построчного формата хранения элементов матрицы [math]L[/math] .
  • Краут-вариант алгоритма Холецкого (Cholesky–Crout algorithm), когда вычисления также начинаются с верхнего левого угла матрицы [math]L[/math] , но проводятся по столбцам. Этот вариант разложения используется несколько реже, применяется он при использовании столбцевого формата хранения элементов матрицы [math]L[/math] , а также когда необходимо проводить коррекцию ведущих элементов при выполнении приближенного разложения.

Оба варианта разложения могут быть применены если требуется построить нижнетреугольный сомножитель [math]L[/math] прямо поверх исходной матрицы [math]A[/math] .

В разделе Разложение Холецкого (метод квадратного корня) подробно рассмотрен базовый точечный вещественный вариант для плотной симметричной положительно определённой матрицы.

1.2 [math]LDL^T[/math] -разложение

Иногда удобнее бывает рассматривать [math]LDL^T[/math] вариант симметричного треугольного разложения, в котором матрица [math]L[/math] является нижней унитреугольной (т.е. имеет единицы на главной диагонали), а [math]D[/math] — диагональная матрица с положительными элементами. В этом варианте разложения легко проследить связь как с ранее рассмотренным [math]LL^T[/math] вариантом:

[math]A = LDL^T = LD^D^L^T = (LD^)\,(LD^)^T = \tilde L \tilde L^T,[/math]

так и с несимметричным [math]LU[/math] -разложением:

[math]A = LDL^T = L(DL^T) = LU.[/math]

2 Разложение Холецкого, блочный вещественный вариант для плотной симметричной положительно определённой матрицы

Можно также рассмотреть блочный вариант разложения Холецкого. Предположим, что [math]n=MN[/math] , тогда исходную матрицу [math]A[/math] размера [math]n\times n[/math] можно представить как блочную матрицу размера [math]N\times N[/math] с блоками размера [math]M\times M[/math] . Все формулы, используемые для получения точечного разложения Холецкого, для блочной матрицы [math]A[/math] останутся практически без изменений. Вместо явного обращения диагональных блоков, эффективнее хранить их в факторизованном виде [math]D_=L_L^T_[/math] , а вместо операции деления использовать соответствующие операции решения для треугольных систем. Общее количество арифметических операций при этом останется практически неизменным, но зато существенно возрастет локальность вычислений. Размер блока [math]M[/math] выбирают таким образом, чтобы все блоки, участвующие в операции исключения, помещались в кэш первого или второго уровня. В этом случае подкачки данных в память будут минимальными.

Аналогичный прием понадобится также и для эффективной реализации параллельной версии разложения Холецкого, что позволит минимизировать как общее количество межпроцессорных обменов, так и количество пересылаемой между процессорами информации. Полезным побочным эффектом применения блочной версии разложения Холецкого может стать повышение скалярной эффективности алгоритма за счет явного использования размера блока [math]M[/math] во внутренних циклах (прием «разворачивание цикла» или «loop unrolling»).

3 Разложение Холецкого, точечный вещественный вариант для разреженной симметричной положительно определённой матрицы

Если исходная матрица [math]A[/math] представлена в разреженном виде, то для экономии памяти, а также арифметических операций, необходимо учитывать ее разреженность.

3.1 Основные отличия от случая плотной матрицы

В этом разделе необходимо рассмотреть матрицы, характеризующиеся способом хранения ненулевых элементов, и имеющие следующие виды разреженности.

  • Лента — матрица, ненулевые элементы которой сосредоточены внутри ленты шириной [math]2d+1[/math] , т.е. когда [math]a_=0[/math] при [math]|i-j| \gt d[/math] . В этом случае, при проведении разложения Холецкого новые ненулевые элементы могут образовываться только внутри этой же ленты (поскольку нет выбора ведущих элементов в силу положительной определенности матрицы [math]A[/math] ). Количество ненулевых элементов в исходной матрице [math]A[/math] , а также в нижнетреугольном множителе [math]L[/math] будет около [math](d+1)n[/math] , а арифметические затраты составят приблизительно [math]d^2n[/math] .
  • Профиль — в более общем случае, заполнение в каждой строке треугольного множителе [math]L[/math] будет определяться позицией первого ненулевого элемента. Сумма по всем строкам расстояний от первого ненулевого элемента строки до главной диагонали и составляет «профиль» матрицы и определяет верхнюю границу количества ненулевых элементов в нижнетреугольном множителе [math]L[/math] .
  • Общая структура разреженности. Верхней границей заполнения треугольного множителя [math]L[/math] , конечно же, будет значение «профиля» матрицы, но учет особенностей структуры ненулевых элементов внутри профиля иногда может дать дополнительный эффект в повышении эффективности вычислений.

При рассмотрении общего случая разреженности необходимо выбрать формат хранения разреженных данных. Таковым может быть, например, формат построчного сжатия данных («compressed sparse row» или CSR формат). В первом вещественном массиве, подряд (обычно в порядке возрастания номеров столбцов) хранятся ненулевые элементы матрицы, во втором, в том же порядке хранятся номера столбцов, в третьем, отдельно сохраняется начало каждой строки. Если общее количество ненулевых элементов в матрице равно nnz («number of nonzeros»), то память для хранения разреженных данных такой матрицы в формате CSR при использовании двойной точности составит [math]3\,+n+1[/math] . Оценку количества арифметических операций в общем случае невозможно, т.к. помимо количества ненулевых элементов в исходной матрице оно существенно зависит от структуры ее разреженности.

Для реализации разложения Холецкого в этом случае понадобится несколько операций с разреженными строками:

  • копирование из одной разреженной строки в другую (или во временный «плотный» вектор, операция распаковки данных);
  • выполнение операции исключения для одного из элементов строки;
  • вставка в строку нового ненулевого элемента («fill-in»);
  • сжатие данных с копированием из временного плотного вектора в сжатый разреженный (операция упаковки данных).

3.2 Переупорядочивания для уменьшения количества новых ненулевых элементов

Структура треугольного множителя [math]L[/math] , а также объем памяти им занимаемый зависят от упорядочивания строк и столбцов исходной матрицы [math]A[/math] , в котором проводилось разложение. Существуют алгоритмы, минимизирующие заполнение матрицы [math]L[/math] .

  • В первую очередь это алгоритм RCM (Reverse Cuthill–McKee), который предназначен для уменьшения профиля матрицы. Одновременно с уменьшением профиля происходит и уменьшение заполнения треугольного множителя [math]L[/math] . Это очень широко применяемый, быстрый, но не самый эффективный алгоритм.
  • Алгоритм вложенных сечений (Nested Dissection, ND) — служит именно для минимизации заполнения множителя [math]L[/math] . В некоторых частных случаях доказана его асимптотическая оптимальность.

В общем случае, проблема поиска перестановки, минимизирующей заполнение множителя [math]L[/math] , является NP-полной задачей.

4 Разложение Холецкого, блочный вещественный вариант для разреженной симметричной положительно определённой матрицы

Иногда разреженную симметричную матрицу бывает удобно представить в блочном виде с блоками небольшого размера [math]M[/math] , равного, например, количеству неизвестных функций на узел при конечно-элементной или конечно-разностной аппроксимации уравнений в частных производных. В этом случае структура разреженности хранится для всей блочной структуры разреженности (что позволяет экономить память на хранении целочисленных массивов). Если общее количество ненулевых блоков размера [math]M\times M[/math] в матрице равно nnz («number of nonzeros»), то память для хранения разреженных данных такой мелкоблочной матрицы в формате CSR при использовании двойной точности составит [math](2M^2+1)\,+n/M+1[/math] .

В некоторых случаях, размер блока [math]M[/math] может выбираться из других соображений, например, для повышения эффективности работы процедур нижнего уровня за счет приема разворачивания циклов (loop unrolling).

Алгоритмы, необходимые при выполнении разложения Холецкого для матриц, рассмотренных в этом разделе, могут быть получены комбинацией уже рассмотренных идей блочности и разреженности.

5 Разложение Холецкого для симметричной незнакоопределенной (седловой) матрицы

Если симметричная матрица [math]<\mathcal A>[/math] представима в виде

где [math]A[/math] — симметричная положительно определенная ( [math]A=A^T\gt 0[/math] ) и [math]C[/math] — симметричная неотрицательно определенная ( [math]C=C^T\ge0[/math] ) матрицы, то, выполнив один шаг блочного исключения, ее можно преобразовать к виду

[math] \begin A & 0 \\ 0 & S \end , [/math]

где матрица дополнения по Шуру [math]S=-(C+B^TA^B)[/math] является строго отрицательно определенной ( [math]S=S^T\lt 0[/math] ). Это означает, что матрица [math]<\mathcal A>[/math] имеет [math]n_A[/math] положительных и [math]n_C[/math] отрицательных собственных значений, где через [math]n_A[/math] и [math]n_C[/math] обозначены размерности матриц [math]A[/math] и [math]C[/math] , соответственно.

В этом случае существует симметричное треугольное разложение вида [math]<\mathcal A>=<\mathcal L>D<\mathcal L>^T[/math] , где [math]<\mathcal L>[/math] является нижней унитреугольной, а диагональная матрица [math]D[/math] содержит [math]n_A[/math] положительных и [math]n_C[/math] отрицательных элементов на главной диагонали, причем такое разложение может быть получено напрямую без выбора ведущего элемента даже если [math]C[/math] — нулевая матрица.

В общем случае разложения невырожденной незнакоопределенной системы необходимо применять выбор ведущего элемента с главной диагонали матрицы, что соответствует некоторой симметричной перестановке строк и столбцов исходной матрицы [math]<\mathcal A>[/math] .

6 Разложение Холецкого для эрмитовой матрицы

Эрмитовой (или комплексно-самосопряженной) матрицей называют такую квадратную комплексную матрицу [math]A[/math] , для элементов которой выполняется соотношение [math]a_=\overline>[/math] (здесь, если [math]z=a+b\,[/math] и [math]^2=-1[/math] , то [math]\overline z=a-b\,[/math] ). В матричном виде это можно записать как [math]A=\overline[/math] или [math]A = A^*[/math] .

6.1 Точечный вариант

Как естественное обобщение точечного разложения Холецкого для симметричной положительно определеной матрицы может быть рассмотрено разложение Холецкого для эрмитовой положительно определеной матрицы. Все формулы для вычисления разложения остаются прежними, только теперь вместо операций над вещественными числами выполняются аналогичные комплексные операции:

В отличие от вещественного варианта, при выполнении аналогичных комплексных операций потребуется считывать из памяти вдвое больше данных и производить над ними примерно вчетверо больше арифметических операций, что должно не только несколько улучшить локальность вычислений, но и повысить общую эффективность вычислений.

6.2 Блочный вариант

Реализация блочного варианта разложения Холецкого для эрмитовых матриц аналогична рассмотренному выше блочному варианту для вещественных матриц.

7 Использование разложения Холецкого в итерационных методах

При выполнении разложения Холецкого в арифметике с фиксированной машинной точностью полученные треугольный фактор [math]L[/math] и само решение может оказаться недостаточно точным. Для получения более точного решения может применяться некоторый итерационный метод (например, метод сопряженных градиентов), с использованием полученного разложения [math]LL^T[/math] в качестве предобусловливателя.

Основной причиной формирование неполного или неточного разложения в качестве предобусловливателя чаще всего бывает требование экономии памяти.

7.1 Ограничивание заполнения в разложении Холецкого

При выполнении разложения Холецкого для разреженной матрицы, может образовываться такое большое количество новых ненулевых элементов, что оперативной памяти на хранение полного разложения окажется недостаточно. В этом случае можно построить неполное или приближенное разложение для применения его в дальнейшем в качестве предобусловливателя. В англоязычной литературе для обозначения таких разложения применяют единый термин Incomplete Cholesky factorization, или сокращенно IC-разложение.

7.2 Неполное разложение Холецкого по позициям IC( [math]k[/math] )

Неполное разложение Холецкого можно получить используя заранее выбранные ограничения по структуре заполнения. Чаще всего получают разложение Холецкого на тех же позициях, в которых находятся ненулевые элементы исходной матрицы [math]A[/math] . Такое разложение обозначают IC(0) или просто IC0.

Если качества разложения IC0 оказывается недостаточно, то можно выбрать более широкую структуру треугольного множителя [math]L[/math] , например, разрешить образование одного уровня новых ненулевых элементов от исходной структуры матрицы [math]A[/math] . Формально, это означает заполнение внутри структуры матрицы [math]A^2[/math] , а такое разложение обозначают IC(1).

Можно рассмотреть и более общий случай, с заполнением внутри структуры матрицы [math]A^[/math] , где [math]k \geq 0[/math] . Такое разложение обозначают IC( [math]k[/math] ).

Обычно с ростом значения [math]k[/math] точность неполного разложения IC( [math]k[/math] ) возрастает, хотя это совсем не является обязательным даже для симметричных положительно определенных матриц, полное разложение для которых существует и находится однозначно. Из-за неполноты разложения на главной диагонали могут оказаться нулевые или даже отрицательные элементы. Чтобы завершить треугольное разложение в таких случаях применяют предварительный диагональный сдвиг исходной матрицы [math]A+\varepsilon I[/math] перед ее разложением. Здесь [math]\varepsilon\gt 0[/math] — малый параметр, а [math]I[/math] — диагональная матрица. Если слишком малый или не положительный диагональный элемент образуется в процессе разложения, то применяют его замену на некоторое заранее выбранное значение. Такую операцию называют диагональной коррекцией разложения.

Неполное разложение IC( [math]k[/math] ) иногда называют также «разложение по позициям».

7.3 Приближенное разложение Холецкого по значениям IC( [math]\tau[/math] )

Для контроля заполнения в треугольном множителе [math]L[/math] разложения Холецкого, кроме структурных ограничений, можно также применить ограничение разложения в зависимости от значения самих элементов разложения. Например, можно сохранять только элементы, большие по модулю чем некоторый малый параметр [math]\tau\gt 0[/math] . В этом случае разложение называют приближенным разложением Холецкого или разложением «по значению» и обозначают IC( [math]\tau[/math] ). Величину [math]\tau[/math] называют «порогом» разложения или «порогом» фильтрации.

Вполне правомерным является ожидание того, что в уменьшением [math]\tau[/math] точность полученного разложения будет возрастать, правда за счет роста количества ненулевых элементов в треугольном множителе [math]L[/math] . Недостатком же такого разложения является то, что, в общем случае, предсказать заполнение [math]L[/math] не возможно.

С точки зрения устойчивости разложения вариант приближенного разложения Холецкого является более предпочтительным, хотя применение предварительного диагонального сдвига, а также диагональной коррекции также допускается. Если же описанные приемы не помогаю получить разложения достаточной точности, то можно применить прием модификации диагонали Азиза-Дженингса, который при отбрасывании малого элемента разложения [math]\ell_[/math] состоит в добавлении модуля этого элемента к диагональным элементам разложения [math]\ell_[/math] и [math]\ell_[/math] . Это прием гарантирует существование приближенного разложения для любой симметричной положительно определенной матрицы [math]A[/math] . Наиболее эффективно этот прием модификации главной диагонали можно организовать при использовании Ктаут-версии разложения Холецкого.

7.4 Приближенное разложение Холецкого второго порядка IC( [math]\tau_1,\tau_2[/math] )

Для повышения точности приближенного разложения можно применить «двухпороговую» версию приближенного разложения Холецкого. Основная идея такого разложения, называемого разложением Тисменецкого-Капорина, состоит в том чтобы вычисление разложения проводить в более высокой точности [math]\tau_2[/math] , а сохранять в треугольном множителе только значения, которые по модулю не меньше [math]\tau_1[/math] . Обычно полагают [math]\tau_1=\tau[/math] и [math]\tau_2=\tau^2[/math] , в этом случае разложение называют разложением «второго порядка», т.к. элементы матрицы ошибок оказываются по модулю меньше чем [math]\tau^2[/math] . Для обозначения симметричного порогового разложения второго порядка используют обозначение IC2, которое не следует путать со структурным разложением IC(2) (т.е. разложением IC( [math]k[/math] ), где [math]k=2[/math] ).

Такое разложение обычно используется вместе с приемом Азиза-Дженингса для модификации диагональных элементов, получая вариант «безотказного» разложения для любой симметричной положительно определенной матрицы [math]A[/math] . Этот вариант разложения позволяет получать наиболее точные разложения (при одинаковом заполнении множителя [math]L[/math] ), хотя для их вычисления приходится тратить больше времени на вычисление самого разложения.

7.5 Комбинация разложений Холецкого IC( [math]k,\tau[/math] ) и IC( [math]\tau,m[/math] )

Для экономии памяти при вычислении неполного или приближенного разложения Холецкого можно использовать следующие два варианта симметричных треугольных разложений.

Для контроля верхней границы заполнения треугольного множителя [math]L[/math] можно предложить использовать заполнение как и для разложения IC( [math]k[/math] ), при некотором выбранном значении [math]k[/math] . Для дальнейшей экономии памяти разложение в заданной структуре разреженности можно вести с использованием порога разложения [math]\tau[/math] , как и при проведении разложения IC( [math]\tau[/math] ). Такую комбинацию можно назвать IC( [math]k,\tau[/math] )-разложением. Применяться она может, например, при необходимости априорных структурных ограничений для минимизации обменов при использовании параллельной версии разложения для распределенной памяти.

Второй вариант структурно-порогового разложения можно описать следующим образом. При проведении обычного порогового IC( [math]\tau[/math] ) разложения, наложим дополнительное ограничение на элементы строк матрицы [math]L[/math] : разрешим сохранение только не более чем [math]m[/math] наибольших по модулю элементов рассматриваемой строки множителя [math]L[/math] . При общей размерности задачи [math]n[/math] в матрице [math]L[/math] будет не более чем [math]nm[/math] элементов. Такой подход представляется разумным, например, для матриц полученных в результате дискретизации с достаточно регулярным шаблоном. Наиболее известен несимметричный вариант такого разложения, предложенного Саадом и называемого ILUT-разложением.

8 Использование разложения Холецкого в параллельных итерационных алгоритмах

Формулы разложения Холецкого по большей части имеют рекурсивный характер и выделение параллельных и независимых этапов вычислений является не очевидной и непростой задачей. Слишком прямолинейное ее решение может привести к значительному объему пересылаемых данных, что значительно снизит результат распараллеливания. Наибольший эффект может дать подход, основанный на предварительном переупорядочивании исходной матрицы.

8.1 Переупорядочивания для выделения блочности

Для того чтобы выделить независимые блоки вычислений, можно использовать симметричные перестановки строк и столбцов исходной матрицы, приводящие ее к блочно окаймленному виду. В этом случае основная часть работы будет сосредоточена в независимых блоках, которые могут обрабатываться параллельно и без обменов данными.

Наиболее простым, но не слишком эффективных способом упорядочивания является предварительное упорядочивание матрицы с помощью обратного алгоритма Катхилла-Макки (RCM, reverse Cuthill—McKee) для минимизации ширины профиля, а затем равномерное разбиение по блокам (процессорам) в новом упорядочивании. После присваивания номера процессора каждой вершине графа матрицы, в независимые блоки можно выделить те вершины графа, которые связаны только с вершинами, имеющими тот же номер процессора (т.е. являющимися внутренними вершинами). Остальные вершины можно объединить в последний блок окаймления, который будет обрабатываться отдельно. Все вычисления внутри блоков будут независимы и могут выполняться параллельно. Для повышения эффективности треугольной факторизации внутренние вершины каждого из блоком можно также упорядочить с помощью метода RCM.

Более эффективными с точки зрения минимизации ширины окаймления будут следущие методы:

  • Метод минимальных сепараторов, который заключается в последовательном нахождении имеющих минимальный размер разделителей (сепараторов), обеспечивающих расщепление оставшихся вершин на два независимых блока.
  • Метод минимальной степени (Minimum Degree, MD). Прямое применение этого метода к матрицах большого размера затруднительно, поэтому используется приближенный метод минимальной степени (Approximate Minimum Degree, AMD).
  • Метод вложенных сечений (Nested Dissection, ND). Это рекурсивный алгоритм, на каждом шаге разделяющий множество вершин на два независимых блока, представленые в [math]2\times2[/math] блочно-окаймленном виде.

В качестве побочного положительного эффекта от такого упорядочивания, для некоторого вида матриц доказано, что полное разложение будет иметь почти минимально возможное количество ненулевых элементов. Нахождение оптимальной перестановки в общем случае является NP-полной задачей.

Существуют и другие алгоритмы упорядочивания матриц для наиболее оптимального их распределения по процессорам. Наиболее популярными являются последовательные пакеты METIS, JOSTLE, SCOTCH, CHACO, PARTY, а также параллельные коды PARMETIS, JOSTLE, PT-SCOTCH и ZOLTAN. Многие из них являются свободно распространяемыми.

8.2 Разложение в независимых блоках

Вычисления в независимых блоках полностью независимы и могут выполняться параллельно без обменов данными между процессорами. Единственным недостатком может быть лишь то, что для пороговых разложений количество арифметических операций на различных процессорах может различаться, что может привести к некоторой несбалансированности вычислений.

8.3 Разложение в сепараторах

Последний блок, в котором собраны сепараторы всех блоков при небольшом количестве используемых процессоров может обрабатываться, например, на одном головном процессоре. Если же процессоров достаточно много, но обработку сепараторов также необходимо производить совместно.

8.4 Иерархические и вложенные алгоритмы

Для обработки сепараторов могут быть применены те же алгоритмы упорядочивания и выделения независимых блоков что и для исходной задачи. Этот же прием может быть применен и на следующем шаге, с получением иерархического или вложенного алгоритма.

В случае применения порогового разложения такие построения могут быть явно применены к построенному дополнению по Шуру. Для структурных факторизаций существуют приложения сразу строящие многоуровневые упорядочивания и обеспечивающие минимальность заполнения и обменов.

8.5 Блочный метод Якоби

Описанные выше подходы относились к типу «прямого» или «явного» разложения, когда при отбрасывании элементов разложения в расчет принимались только их абсолютные значения. Структурные свойства при этом являлись подчиненными и на отбрасывание элементов никак не влияли.

Альтернативным является подход, когда из-за соображений увеличения ресурса параллелизма некоторые элементы отбрасываются исключительно из структурных соображений. Например, можно сначала распределить строки матрицы по процессорам, а затем перед проведением разложения просто отбросить все элементы связывающие один процессор с другим. В этом случае разложение будет проходить полностью независимо в каждом из блоков. Внутри каждого блока может проводиться любой из структурных или пороговых вариантов разложения Холецкого. Построение такого предобусловливателя называют блочным методом Якоби без перекрытия блоков (Block Jacobi, BJ). Такое предобусловливание является наиболее простым, применение его наиболее параллельным (полностью без обменов данными), правда сходимость может оставлять желать лучшего, почти независимо от качества разложения внутри каждого из блоков.

8.6 Аддитивный метод Шварца

Разложение гораздо более высокого качества по сравнению с методом Якоби можно получить применяя аддитивный метод Шварца (Additive Schwarz, AS). Иногда этот метод называют также методом Якоби с перекрытиями. Суть его заключается в расширении структуры каждого из блоков матрицы за счет добавления нескольких слоев близлежащих строк матрицы. Треугольное разложение строится для расширенной матрицы, таким образом на каждом из процессоров происходит решение расширенной подзадачи с привлечением данных от других процессоров. После нахождения решения подзадачи на каждом из процессоров обычно происходит отбрасывание не локальных компонент решения. Такой вариант метода называют аддитивный метод Шварца с ограничениями (Restricted Additive Schwarz, RAS).

Сходимость аддитивного метода Шварца бывает гораздо выше чем сходимость метода Якоби, и обычно монотонно улучшается с ростом размера перекрытия. Несмотря на дополнительные вычисление и обмены, общее время решения на параллельном компьютере может быть существенно меньше.

8.7 Неполное обратное треугольное разложения

Существует и другой вариант аддитивного разложения, который кроме несколько более быстрой сходимости опирается на построение перекрытий блоков только в одну сторону («назад», т.е. в сторону меньших номеров строк). Название этого метода блочное неполного обратного разложения Холецкого, имеющее только английскую аббревиатуру BIIC (Block Incomplete Inverse Cholesky). Позднее, вместе с рассмотрением несимметричного варианта разложения (BIILU), этот метод стал называться методом неполного обратного треугольного разложения, или НОТ-разложения.

Комбинация этого метода с неполным симметричным треугольным разложением второго порядка IC2 внутри каждого из блоков имеет обозначение BIIC2.

Идея этого метода впервые была предложена И.Е.Капориным в виде последовательного алгоритма. В литературе встречается также название этого метода как метод Капорина-Коньшина, по имени авторов впервые представивших его параллельную реализацию и проанализировавших ее свойства.

9 Решение линейных систем с треугольной матрицей

Разложение Холецкого может применяться для решения системы линейных уравнений [math]Ax = b[/math] , если матрица [math]A[/math] симметрична и положительно определена. Выполнив разложение [math]A = LL^T[/math] , решение [math]x[/math] получается последовательным решением двух треугольных систем уравнений [math]Ly = b[/math] и [math]L^T x = y[/math] .

9.1 Решение системы с плотной нижнетреугольной матрицей

Решение линейной системы с плотной нижнетреугольной матрицей [math]L y = b[/math] можно представить в виде «прямого» хода, т.е. цепочки вычислений, начиная с верхнего угла матрицы [math]L[/math] по возрастанию номера строки [math]i[/math] :

[math] \begin y_ & = b_, \\ y_ & = b_ — \sum_^ \ell_ y_, \quad i = 2. n. \end [/math]

В разделе Прямая_подстановка_(вещественный_вариант) содержится подробное описание алгоритма и его анализ.

9.2 Решение системы с плотной верхнетреугольной матрицей

Решение линейной системы с плотной верхнетреугольной матрицей [math]U x = y[/math] (где, например, [math]U=L^T[/math] ) можно представить в виде «обратного» хода, т.е. цепочки вычислений, начиная с нижнего угла матрицы [math]U[/math] при убываниии номера строки [math]i[/math] :

[math] \begin x_ & = y_/u_, \\ x_ & = \left (y_ — \sum_^ u_ x_ \right ) / u_, \quad i = n — 1. 1. \end [/math]

В разделе Обратная_подстановка_(вещественный_вариант) содержится подробное описание алгоритма и его анализ.

9.3 Решение системы с разреженной нижнетреугольной матрицей

Решение линейных систем с разреженной нижне- или верхнетреугольной матрицей аналогично рассмотренным алгоритмам для плотных матриц, при этом подстановки ведутся исключительно для ненулевых элементов с учетом идеи работы с разреженными матрицами.

9.4 Решение системы с комплексной треугольной матрицей

Решение линейных систем с комплексной нижне- или верхнетреугольной матрицей аналогично рассмотренным алгоритмам для вещественных матриц, при этом арифметические операции выполняются в комплексной арифметике, аналогично операциям раздела факторизации эрмитовых матриц.

9.5 Решение систем с блочноокаймленными треугольными матрицами

Особенность решения линейных систем с блочноокаймленными треугольными матрицами в том что независимость вычислений в отдельных блоках дает возможность проведения параллельных вычислений.

10 Существующие реализации алгоритма

  • В LAPACK используется функция DPBTRF (последовательная реализация для двойной точности).
  • В ScaLAPACK используется функция PDPBTRF (параллельная реализация для двойной точности).
  • В SAS используется функция ROOT( matrix ), входящая в пакет SAS IML.
  • В системах MATLAB, Octave, R разложение выполняется командой U = chol(A).
  • В Maple и NumPy существует процедура cholesky в модуле linalg.
  • В Mathematica используется процедура CholeskyDecomposition[A].
  • В GSL используется функция gsl_linalg_cholesky_decomp.
  • В ALGLIB имеются реализации как LLT так и LDLT разложений для различных языков программирования: C#, C++, C++ (арифметика повышенной точности), FreePascal, Delphi, VB.NET, VBA, Python.
  • В Online Matrix Calculator непосредственно в web-интерфейсе можно выполнить разложение Холецкого, выбрав раздел Cholesky Decomposition.
  • Уровень метода
  • Законченные статьи
  • Разложения матриц

OLED и LED телевизоры – в чем разница?

Когда встает вопрос о покупке нового телевизора LG, многие покупатели сталкиваются с проблемой выбора технологии создания изображения на экране. В этой статье мы рассмотрим, чем отличаются OLED и LED телевизоры.

ЖК телевизоры от компании LG представляют собой матрицу из пикселей, содержащую жидкие кристаллы RGB красного, синего и зеленого цвета. Под воздействием напряжения пиксели матрицы меняют расположение: пропускают или блокируют подсветку. ЖК кристаллы или квантовые точки сами не производят свет, их называют пропускающими. Поэтому им нужен внешний источник, который может быть:

  • Флуоресцентным.
  • Либо когда источником выступают светодиоды.

В зависимости от того, какой источник используется, образуются разные типы ЖК экранов. Современный рынок предлагает три ведущих технологии ЖК телевизоров от компании LG, каждая из которых отличается принципом работы и стоимостью:

  • LCD – первый тип ЖК-панели, его отличие заключается в низкой стоимости и простом наборе функций. В настоящее время LCD модели телевизора считаются устаревшими. Подсветка экранов в LCD устройствах осуществляется с помощью флуоресцентных ламп.
  • LED панели – усовершенствованные модели телевизора LG, разработанные на базе LCD, но обладающие более высокими параметрами четкости и разрешения. Аббревиатура LED расшифровывается как «Light-emitting diode». LED модели являются одним из типов подсветки LCD панелей, основанного на работе светодиодов. При этом светодиоды могут быть расположены как в торцевой части, так и равномерно распределены по всей матрице экрана. По стоимости LED телевизор будет дороже, чем LCD, но и качество изображения у него будет выше.
  • OLED технология. Использует для освещения экрана пленку из органических светодиодов. OLED освещение образуется из нескольких слоев органических полимеров, способных излучать свет при подаче на них электрического тока. Малые размеры отдельных соединений позволяют создавать на их основе пиксельные матрицы. Отличие технологии OLED от LED заключается в том, что OLED устройства не нуждаются в дополнительной подсветке дисплея, так как свечение испускает каждый пиксель, что выводит качество изображения ЖК телевизора на новый уровень. OLED телевизор также отличают большие диагонали. Цена OLED телевизоров несколько выше предыдущих типов.

Разница между моделями телевизоров от компании LG с технологиями LED и OLED достаточно существенна. В классической LED панели излучатели телевизора используются исключительно для создания подсветки. Цветопередача телевизора регулируется жидкокристаллической матрицей и пикселями полимерных материалов.

В OLED панели, выполненной на основе органических светодиодов, каждая ячейка — это самостоятельный источник света размером в 1 пиксель. Данная технология не требует создания жидкокристаллического затвора, дополнительной подсветки и управления цветом при помощи полимерных светофильтров, что позволяет значительно уменьшить толщину дисплея.

Рассмотрим отличие характеристик телевизоров LG с LED и OLED технологией:

Цветопередача. По этому параметру отличие LED экрана телевизора LG от OLED дисплея телевизора LG проявляется в методике передачи цвета. В LED панели каждый светодиод имеет свой конкретный цвет. Оттенки образуются путем усиления или прекращения подачи тока на элементы квантовых точек. При использовании светофильтров окрас задается через них. Пиксели в OLED матрице содержат основные цвета и формируют из них комбинации для отображения нужной цветопередачи.

Контрастность и уровень черного цвета. Контрастность изображения – это соотношение уровня черного к белому. В OLED экранах телевизора LG органические светодиоды представляют собой самостоятельные источники света, где яркость и уровень контрастности свечения регулируется индивидуально. Поэтому при деактивации элементов матрицы уровень контрастности черного будет абсолютным, чего не скажешь о LED дисплеях, где присутствует проникновение света от подсветки. Подсветка работает, даже если изображение на экране с LED технологией полностью затемнено при помощи организованных в соответствующие формы жидких кристаллов. Передача черного цвета образуется путем перекрытия кристаллами источника света. Это заставляет чёрный цвет выглядеть блекло и делает дискомфортным просмотр сцен, снятых в ночи или при приглушенном освещении.

Разрешение. Производитель LG в каждом телевизоре с технологиями LED и OLED использует идентичные параметры разрешения матрицы 3840 х 2160 пикселей. Однако размеры органических светодиодов равны 1 пикселю (OLED), что значительно меньше размеров классических светодиодов (LED). Это позволяет при одинаковом разрешении экрана телевизора увеличить плотность источников света, а, значит, и качество изображения у OLED-экрана будет лучше.

Время отклика пикселей. Время отклика – это промежуток времени между вводом информации и реакцией устройства. В ЖК-дисплее телевизора от компании LG это время определяет скорость, с которой пиксель меняет яркость под действием электрического сигнала. Низкое время отклика означает отсутствие притормаживания. Чем меньше время отклика, тем меньше глаз будет замечать искажений при просмотре динамичного видео.

Разница модели LED телевизора с OLED телевизором состоит в том, что изображение в OLED дисплее формируется органическими светодиодами без посредников, которые обладают одной особенностью: смена цвета и яркости происходит молниеносно, что обеспечивает минимальное время отклика и отсутствие даже при демонстрации самых динамичных сцен. Таким образом, скорость передачи света становится выше. Благодаря этому при просмотре OLED телевизора увеличивается скорость смены кадров и повышается уровень комфорта.

Угол обзора. Если смотреть на экран LED телевизора LG со стороны, то можно обратить внимание на то, что изображение подвержено искажениям. Контрастность и передача цвета меняются в зависимости от угла обзора. Это происходит из-за рассеивания подсветки. Устройства выпускаются в расчете на то, что взгляд зрителя будет располагаться под прямым углом обзора от экрана. Экран OLED телевизора LG обеспечивает четкое изображение без искажений под любым углом обзора. Изображение будет одинаково подсвечено со всех сторон.

Остаточное изображение. Характерно для всех экранов OLED телевизора. Органические излучающие полупроводники склонны к демонстрации остаточного изображения при длительном просмотре статичной картинки на экране. Такой эффект происходит из-за естественного износа излучателя, который при постоянной работе тускнеет раньше менее используемых пикселей. На практике это выглядит в виде остаточного изображения логотипа канала, который, как правило, находится в статичном положении. В современных устройствах через некоторое время данный логотип исчезает самостоятельно, но при выборе телевизора потребителю следует знать о существовании такой особенности.

Стоит отметить, что остаточное изображение проявляется и на LED панелях, только для достижения подобного эффекта потребуется значительно больше времени.

Энергопотребление. В настоящее время энергоэффективность телевизоров LG является одним из наиболее значимым параметром, учитывая постоянный рост стоимости электроэнергии. Отличие LED телевизора от OLED заключается в наличии подсветки у LED дисплеев устройств.

Телевизор с LED технологией тратит электроэнергию согласно уровню яркости установленной подсветки. Владелец устройства может вручную переустанавливать интенсивность освещенности сцен в видео. В норме для питания диагонали в 55 дюймов уходит 80-150 Вт. На диагональ 65 дюймов нужно 110-180 Вт. Формат HDR расходует больше энергии и разница составляет 40-90 Вт.

На потребление электричества OLED телевизоров влияет непосредственно яркость передаваемого изображения. Уровень энергопотребления колеблется в зависимости от освещенности сцен в видео. Устройство в 55 дюймов по диагонали обычно использует примерно 80-150 Вт, а для работы телевизора с диагональю 65 дюймов потребуется 110-180 Вт. В формате HDR энергопотребление поднимается на 20-50 Вт.

Срок службы. Для экранов телевизора показатель срока службы означает время, через которое экран «выгорит», то есть утратит половину начального значения яркости цветов. Экран OLED-телевизора рассчитан примерно на 30 тысяч часов. LED-панели отличаются заявленным сроком службы примерно 50-100 тысяч часов.

Стоимость. Выбирая модель телевизора LG следует учитывать, что между LED и OLED технологиями разница в цене может быть весьма значительна. Стоимость OLED телевизора может в 3-4 раза превышать цену LED устройств.

Покупатель может с легкостью подобрать телевизор с LED технологией с необходимыми функциями под свой индивидуальный бюджет. Достаточно сосредоточиться на приоритетных параметрах: модель от известного производителя, долгий срок гарантийного обслуживания или качество изображения. Большая популярность, отлаженное серийное производство и постепенное устаревание технологии приводят к падению цен и на устройства с большой диагональю. Кроме того, благодаря непрекращающимся усилиям производителей по совершенствованию своей продукции качественное отличие LED от OLED технологий немного сглаживается.

Габариты панели. С каждым годом в линейке телевизоров LG с классической светодиодной матрицей появляются все новые модели с увеличенной диагональю дисплея. Однако многослойная конструкция экрана не позволяет снизить толщину и вес телевизора. Конструктивная особенность OLED дисплеев – это отсутствие дополнительной жидкокристаллической сетки и полимерных светофильтров. Поэтому вес и толщина OLED устройств будет меньше, чем у LED телевизоров. Тем не менее диагональ OLED телевизоров в среднем доходит до 60 дюймов, что не идет ни в какое сравнение с LED моделями.

Если подвести итог, то можно выделить следующее:

  • LED-модели выгоднее по ценовым параметрам, их отличает широкий выбор моделей и длительный срок эксплуатации.
  • OLED-телевизоры показывают впечатляющие результаты по скорости отклика, их отличает широкие углы обзора, большая яркость и контрастность изображения. Однако OLED имеет более короткий срок службы устройства, стоимость его будет выше, а выбор размера диагонали ограничен.

Выбор телевизора – задача весьма ответственная, ведь техника покупается на годы вперед. Именно поэтому целесообразно не экономить, а отдавать предпочтение новейшим технологиям, ведь рынок только развивается. Стоит ли покупать OLED телевизор – решать только вам. Но помните, что LED – это уже хорошо известная технология, у которой вряд ли остался потенциал двигаться вперед, в то время как у молодой и перспективной OLED технологии все только начинается.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *