Java Vector внутренние продукты

Question

У меня есть массив m-мерных векторов (хранится как простые массивы) v1, v2 ... vn.

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

Один из способов сделать это - простой цикл for для всех его компонентов.

double sum=0;
for(int i=0; i<m; i++)
    sum+=v1[i]*v2[i];

Это практически единственная операция по линейной алгебре, которую я намереваюсь выполнить над своими данными.

1. Будет ли эффективнее импортировать библиотеку linalg, такую ​​как JAMA или la4j, хранить все как матрицы и вычислять внутренние продукты? (это даже не большие умножения матриц, а только внутренние произведения между одномерными векторами)

2. Как la4j(и т. Д.) Реализует точечный продукт? Разве он не будет перебирать каждый индекс и умножать каждую пару компонентов?

Answer 1

la4j является открытым исходным кодом, посмотрите на код. С использованием AbstractVectorВнутренний продукт менее эффективен, чем ваш собственный код, поскольку он создает дополнительные объекты операций, здесь OoPlaceInnerProduct.

Однако: в большинстве случаев я все же предпочел бы использовать существующий, хорошо протестированный пакет векторной математики, чем реализовывать свой собственный. (Кнут: "Мы должны забыть о малой эффективности, скажем, в 97% случаев: преждевременная оптимизация - корень всего зла".)

Обратите внимание, что многопоточность тоже не помогает. Даже высокоэффективный LAPACK Пакет использует тот же код, что и ваш.

Answer 2

Что касается библиотеки la4j: в новой версии 0.5.0 используются облегченные разреженные итерации, поэтому вам не нужно беспокоиться о переборе нулевых значений в разреженных векторах. Вот пример API

Vector a = new BasicVector(...); // dense
Vector b = new CompressedVector(...); // sparse
double dot = a.innerProduct(b);

Вы можете объединить любую возможную пару: разреженно-разреженный, разреженно-разреженный, плотно-плотный, плотно-разреженный. Библиотека la4j всегда будет использовать наиболее эффективный алгоритм в зависимости от ваших данных.

Answer 3

Если вы хотите вычислить все внутренние продукты, я рекомендую это: в матрице A храните ваши векторы в строках, а в B - в столбцах. Тогда в A*B вы будете иметь положение (i,j) внутреннего произведения v_i и v_j.

Хитрость в том, что нормальное матричное умножение занимает n^3 времени, но некоторые умные алгоритмы имеют более эффективные методы, но только для ~ 30 и более векторов.