1 /* 2 * This file is part of ELKI: 3 * Environment for Developing KDD-Applications Supported by Index-Structures 4 * 5 * Copyright (C) 2018 6 * ELKI Development Team 7 * 8 * This program is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU Affero General Public License as published by 10 * the Free Software Foundation, either version 3 of the License, or 11 * (at your option) any later version. 12 * 13 * This program is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU Affero General Public License for more details. 17 * 18 * You should have received a copy of the GNU Affero General Public License 19 * along with this program. If not, see <http://www.gnu.org/licenses/>. 20 */ 21 package de.lmu.ifi.dbs.elki.math.linearalgebra; 22 23 import java.util.Arrays; 24 25 import de.lmu.ifi.dbs.elki.utilities.documentation.Reference; 26 import de.lmu.ifi.dbs.elki.utilities.documentation.Title; 27 import net.jafama.FastMath; 28 29 /** 30 * Class providing basic vector mathematics, for low-level vectors stored as 31 * {@code double[]}. While this is less nice syntactically, it reduces memory 32 * usage and VM overhead. 33 * 34 * @author Erich Schubert 35 * @since 0.5.0 36 * 37 * @opt nodefillcolor LemonChiffon 38 */ 39 @Title("Vector and Matrix Math Library") 40 public final class VMath { 41 /** 42 * A small number to handle numbers near 0 as 0. 43 */ 44 private static final double DELTA = 1E-5; 45 46 /** 47 * Error message when vector dimensionalities do not agree. 48 */ 49 protected static final String ERR_VEC_DIMENSIONS = "Vector dimensions do not agree."; 50 51 /** 52 * Error message when matrix dimensionalities do not agree. 53 */ 54 protected static final String ERR_MATRIX_DIMENSIONS = "Matrix dimensions do not agree."; 55 56 /** 57 * Error message when matrix dimensionalities do not agree. 58 */ 59 protected static final String ERR_MATRIX_INNERDIM = "Matrix inner dimensions do not agree."; 60 61 /** 62 * Error message when dimensionalities do not agree. 63 */ 64 protected static final String ERR_DIMENSIONS = "Dimensionalities do not agree."; 65 66 /** 67 * Error message when min > max is given as a range. 68 */ 69 protected static final String ERR_INVALID_RANGE = "Invalid range parameters."; 70 71 /** 72 * Error when a non-square matrix is used with determinant. 73 */ 74 protected static final String ERR_MATRIX_NONSQUARE = "Matrix must be square."; 75 76 /** 77 * Error with a singular matrix. 78 */ 79 protected static final String ERR_SINGULAR = "Matrix is singular."; 80 81 /** 82 * When a symmetric positive definite matrix is required. 83 */ 84 protected static final String ERR_MATRIX_NOT_SPD = "Matrix is not symmetric positive definite."; 85 86 /** 87 * When a matrix is rank deficient. 88 */ 89 protected static final String ERR_MATRIX_RANK_DEFICIENT = "Matrix is rank deficient."; 90 91 /** 92 * Fake constructor. Static class. 93 */ VMath()94 private VMath() { 95 // Cannot be instantiated 96 } 97 98 /** 99 * Returns the ith unit vector of the specified dimensionality. 100 * 101 * @param dimensionality the dimensionality of the vector 102 * @param i the index 103 * @return the ith unit vector of the specified dimensionality 104 */ unitVector(final int dimensionality, final int i)105 public static double[] unitVector(final int dimensionality, final int i) { 106 final double[] v = new double[dimensionality]; 107 v[i] = 1; 108 return v; 109 } 110 111 /** 112 * Returns a copy of this vector. 113 * 114 * @param v original vector 115 * @return a copy of this vector 116 */ copy(final double[] v)117 public static double[] copy(final double[] v) { 118 return v.clone(); 119 } 120 121 /** 122 * Transpose vector to a matrix <em>without copying</em>. 123 * 124 * @param v Vector 125 * @return Matrix 126 */ transpose(final double[] v)127 public static double[][] transpose(final double[] v) { 128 return new double[][] { v }; 129 } 130 131 /** 132 * Computes component-wise v1 + v2 for vectors. 133 * 134 * @param v1 first vector 135 * @param v2 second vector 136 * @return the sum v1 + v2 137 */ plus(final double[] v1, final double[] v2)138 public static double[] plus(final double[] v1, final double[] v2) { 139 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 140 final double[] result = new double[v1.length]; 141 for(int i = 0; i < result.length; i++) { 142 result[i] = v1[i] + v2[i]; 143 } 144 return result; 145 } 146 147 /** 148 * Computes component-wise v1 + v2 * s2. 149 * 150 * @param v1 first vector 151 * @param v2 second vector 152 * @param s2 the scalar 153 * @return the result of v1 + v2 * s2 154 */ plusTimes(final double[] v1, final double[] v2, final double s2)155 public static double[] plusTimes(final double[] v1, final double[] v2, final double s2) { 156 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 157 final double[] result = new double[v1.length]; 158 for(int i = 0; i < result.length; i++) { 159 result[i] = v1[i] + v2[i] * s2; 160 } 161 return result; 162 } 163 164 /** 165 * Computes component-wise v1 * s1 + v2. 166 * 167 * @param v1 first vector 168 * @param s1 the scalar for v1 169 * @param v2 second vector 170 * @return the result of v1 * s1 + v2 171 */ timesPlus(final double[] v1, final double s1, final double[] v2)172 public static double[] timesPlus(final double[] v1, final double s1, final double[] v2) { 173 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 174 final double[] result = new double[v1.length]; 175 for(int i = 0; i < result.length; i++) { 176 result[i] = v1[i] * s1 + v2[i]; 177 } 178 return result; 179 } 180 181 /** 182 * Computes component-wise v1 * s1 + v2 * s2. 183 * 184 * @param v1 first vector 185 * @param s1 the scalar for v1 186 * @param v2 second vector 187 * @param s2 the scalar for v2 188 * @return the result of v1 * s1 + v2 * s2 189 */ timesPlusTimes(final double[] v1, final double s1, final double[] v2, final double s2)190 public static double[] timesPlusTimes(final double[] v1, final double s1, final double[] v2, final double s2) { 191 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 192 final double[] result = new double[v1.length]; 193 for(int i = 0; i < result.length; i++) { 194 result[i] = v1[i] * s1 + v2[i] * s2; 195 } 196 return result; 197 } 198 199 /** 200 * Computes component-wise v1 = v1 + v2, 201 * overwriting the vector v1. 202 * 203 * @param v1 first vector (overwritten) 204 * @param v2 second vector 205 * @return v1 = v1 + v2 206 */ plusEquals(final double[] v1, final double[] v2)207 public static double[] plusEquals(final double[] v1, final double[] v2) { 208 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 209 for(int i = 0; i < v1.length; i++) { 210 v1[i] += v2[i]; 211 } 212 return v1; 213 } 214 215 /** 216 * Computes component-wise v1 = v1 + v2 * s2, 217 * overwriting the vector v1. 218 * 219 * @param v1 first vector (overwritten) 220 * @param v2 another vector 221 * @param s2 scalar factor for v2 222 * @return v1 = v1 + v2 * s2 223 */ plusTimesEquals(final double[] v1, final double[] v2, final double s2)224 public static double[] plusTimesEquals(final double[] v1, final double[] v2, final double s2) { 225 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 226 for(int i = 0; i < v1.length; i++) { 227 v1[i] += s2 * v2[i]; 228 } 229 return v1; 230 } 231 232 /** 233 * Computes component-wise v1 = v1 * s1 + v2, 234 * overwriting the vector v1. 235 * 236 * @param v1 first vector (overwritten) 237 * @param s1 scalar factor for v1 238 * @param v2 another vector 239 * @return v1 = v1 * s1 + v2 240 */ timesPlusEquals(final double[] v1, final double s1, final double[] v2)241 public static double[] timesPlusEquals(final double[] v1, final double s1, final double[] v2) { 242 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 243 for(int i = 0; i < v1.length; i++) { 244 v1[i] = v1[i] * s1 + v2[i]; 245 } 246 return v1; 247 } 248 249 /** 250 * Computes component-wise v1 = v1 * s1 + v2 * s2, 251 * overwriting the vector v1. 252 * 253 * @param v1 first vector (overwritten) 254 * @param s1 scalar for v1 255 * @param v2 another vector 256 * @param s2 scalar for v2 257 * @return v1 = v1 * s1 + v2 * s2 258 */ timesPlusTimesEquals(final double[] v1, final double s1, final double[] v2, final double s2)259 public static double[] timesPlusTimesEquals(final double[] v1, final double s1, final double[] v2, final double s2) { 260 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 261 for(int i = 0; i < v1.length; i++) { 262 v1[i] = v1[i] * s1 + v2[i] * s2; 263 } 264 return v1; 265 } 266 267 /** 268 * Computes component-wise v1 + s1. 269 * 270 * @param v1 vector to add to 271 * @param s1 constant value to add 272 * @return v1 + s1 273 */ plus(final double[] v1, final double s1)274 public static double[] plus(final double[] v1, final double s1) { 275 final double[] result = new double[v1.length]; 276 for(int i = 0; i < result.length; i++) { 277 result[i] = v1[i] + s1; 278 } 279 return result; 280 } 281 282 /** 283 * Computes component-wise v1 = v1 + s1, 284 * overwriting the vector v1. 285 * 286 * @param v1 vector to add to (overwritten) 287 * @param s1 constant value to add 288 * @return Modified vector 289 */ plusEquals(final double[] v1, final double s1)290 public static double[] plusEquals(final double[] v1, final double s1) { 291 for(int i = 0; i < v1.length; i++) { 292 v1[i] += s1; 293 } 294 return v1; 295 } 296 297 /** 298 * Computes component-wise v1 - v2. 299 * 300 * @param v1 first vector 301 * @param v2 the vector to be subtracted from this vector 302 * @return v1 - v2 303 */ minus(final double[] v1, final double[] v2)304 public static double[] minus(final double[] v1, final double[] v2) { 305 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 306 final double[] sub = new double[v1.length]; 307 for(int i = 0; i < v1.length; i++) { 308 sub[i] = v1[i] - v2[i]; 309 } 310 return sub; 311 } 312 313 /** 314 * Computes component-wise v1 - v2 * s2. 315 * 316 * @param v1 first vector 317 * @param v2 the vector to be subtracted from this vector 318 * @param s2 the scaling factor for v2 319 * @return v1 - v2 * s2 320 */ minusTimes(final double[] v1, final double[] v2, final double s2)321 public static double[] minusTimes(final double[] v1, final double[] v2, final double s2) { 322 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 323 final double[] sub = new double[v1.length]; 324 for(int i = 0; i < v1.length; i++) { 325 sub[i] = v1[i] - v2[i] * s2; 326 } 327 return sub; 328 } 329 330 /** 331 * Computes component-wise v1 * s1 - v2. 332 * 333 * @param v1 first vector 334 * @param s1 the scaling factor for v1 335 * @param v2 the vector to be subtracted from this vector 336 * @return v1 * s1 - v2 337 */ timesMinus(final double[] v1, final double s1, final double[] v2)338 public static double[] timesMinus(final double[] v1, final double s1, final double[] v2) { 339 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 340 final double[] sub = new double[v1.length]; 341 for(int i = 0; i < v1.length; i++) { 342 sub[i] = v1[i] * s1 - v2[i]; 343 } 344 return sub; 345 } 346 347 /** 348 * Computes component-wise v1 * s1 - v2 * s2. 349 * 350 * @param v1 first vector 351 * @param s1 the scaling factor for v1 352 * @param v2 the vector to be subtracted from this vector 353 * @param s2 the scaling factor for v2 354 * @return v1 * s1 - v2 * s2 355 */ timesMinusTimes(final double[] v1, final double s1, final double[] v2, final double s2)356 public static double[] timesMinusTimes(final double[] v1, final double s1, final double[] v2, final double s2) { 357 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 358 final double[] sub = new double[v1.length]; 359 for(int i = 0; i < v1.length; i++) { 360 sub[i] = v1[i] * s1 - v2[i] * s2; 361 } 362 return sub; 363 } 364 365 /** 366 * Computes component-wise v1 = v1 - v2, 367 * overwriting the vector v1. 368 * 369 * @param v1 vector 370 * @param v2 another vector 371 * @return v1 = v1 - v2 372 */ minusEquals(final double[] v1, final double[] v2)373 public static double[] minusEquals(final double[] v1, final double[] v2) { 374 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 375 for(int i = 0; i < v1.length; i++) { 376 v1[i] -= v2[i]; 377 } 378 return v1; 379 } 380 381 /** 382 * Computes component-wise v1 = v1 - v2 * s2, 383 * overwriting the vector v1. 384 * 385 * @param v1 vector 386 * @param v2 another vector 387 * @param s2 scalar for v2 388 * @return v1 = v1 - v2 * s2 389 */ minusTimesEquals(final double[] v1, final double[] v2, final double s2)390 public static double[] minusTimesEquals(final double[] v1, final double[] v2, final double s2) { 391 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 392 for(int i = 0; i < v1.length; i++) { 393 v1[i] -= v2[i] * s2; 394 } 395 return v1; 396 } 397 398 /** 399 * Computes component-wise v1 = v1 * s1 - v2, 400 * overwriting the vector v1. 401 * 402 * @param v1 vector 403 * @param s1 scalar for v1 404 * @param v2 another vector 405 * @return v1 = v1 * s1 - v2 406 */ timesMinusEquals(final double[] v1, final double s1, final double[] v2)407 public static double[] timesMinusEquals(final double[] v1, final double s1, final double[] v2) { 408 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 409 for(int i = 0; i < v1.length; i++) { 410 v1[i] = v1[i] * s1 - v2[i]; 411 } 412 return v1; 413 } 414 415 /** 416 * Computes component-wise v1 = v1 * s1 - v2 * s2, 417 * overwriting the vector v1. 418 * 419 * @param v1 vector 420 * @param s1 scalar for v1 421 * @param v2 another vector 422 * @param s2 Scalar 423 * @return v1 = v1 * s1 - v2 * s2 424 */ timesMinusTimesEquals(final double[] v1, final double s1, final double[] v2, final double s2)425 public static double[] timesMinusTimesEquals(final double[] v1, final double s1, final double[] v2, final double s2) { 426 assert v1.length == v2.length : ERR_VEC_DIMENSIONS; 427 for(int i = 0; i < v1.length; i++) { 428 v1[i] = v1[i] * s1 - v2[i] * s2; 429 } 430 return v1; 431 } 432 433 /** 434 * Subtract component-wise v1 - s1. 435 * 436 * @param v1 original vector 437 * @param s1 Value to subtract 438 * @return v1 - s1 439 */ minus(final double[] v1, final double s1)440 public static double[] minus(final double[] v1, final double s1) { 441 final double[] result = new double[v1.length]; 442 for(int i = 0; i < v1.length; i++) { 443 result[i] = v1[i] - s1; 444 } 445 return result; 446 } 447 448 /** 449 * Subtract component-wise in-place v1 = v1 - s1, 450 * overwriting the vector v1. 451 * 452 * @param v1 original vector 453 * @param s1 Value to subtract 454 * @return v1 = v1 - s1 455 */ minusEquals(final double[] v1, final double s1)456 public static double[] minusEquals(final double[] v1, final double s1) { 457 for(int i = 0; i < v1.length; i++) { 458 v1[i] -= s1; 459 } 460 return v1; 461 } 462 463 /** 464 * Multiply component-wise v1 * s1. 465 * 466 * @param v1 original vector 467 * @param s1 the scalar to be multiplied 468 * @return v1 * s1 469 */ times(final double[] v1, final double s1)470 public static double[] times(final double[] v1, final double s1) { 471 final double[] v = new double[v1.length]; 472 for(int i = 0; i < v1.length; i++) { 473 v[i] = v1[i] * s1; 474 } 475 return v; 476 } 477 478 /** 479 * Multiply component-wise v1 = v1 * s1, 480 * overwriting the vector v1. 481 * 482 * @param v1 original vector 483 * @param s scalar 484 * @return v1 = v1 * s1 485 */ timesEquals(final double[] v1, final double s)486 public static double[] timesEquals(final double[] v1, final double s) { 487 for(int i = 0; i < v1.length; i++) { 488 v1[i] *= s; 489 } 490 return v1; 491 } 492 493 /** 494 * Multiply component-wise v1 = v2 * s, 495 * overwriting the vector v1. 496 * 497 * @param v1 output vector 498 * @param v2 input vector 499 * @param s scalar 500 * @return v1 with new values 501 */ overwriteTimes(final double[] v1, final double[] v2, final double s)502 public static double[] overwriteTimes(final double[] v1, final double[] v2, final double s) { 503 for(int i = 0; i < v1.length; i++) { 504 v1[i] = v2[i] * s; 505 } 506 return v1; 507 } 508 509 /** 510 * Matrix multiplication: v1 * m2 (m2 <em>must have one row only</em>). 511 * <p> 512 * Note: this is an unusual operation, m2 must be a costly column matrix. 513 * <p> 514 * This method is equivalent to the 515 * {@link #timesTranspose(double[], double[])} method 516 * with m2 being the second vector as matrix, but transposed. 517 * 518 * @param v1 vector 519 * @param m2 other matrix, must have one row. 520 * @return Matrix product, v1 * m2 521 * @deprecated this is fairly inefficient memory layout, rewriting your code 522 */ 523 @Deprecated times(final double[] v1, final double[][] m2)524 public static double[][] times(final double[] v1, final double[][] m2) { 525 assert m2.length == 1 : ERR_MATRIX_INNERDIM; 526 final int columndimension = m2[0].length; 527 final double[][] re = new double[v1.length][columndimension]; 528 for(int j = 0; j < columndimension; j++) { 529 for(int i = 0; i < v1.length; i++) { 530 re[i][j] = v1[i] * m2[0][j]; 531 } 532 } 533 return re; 534 } 535 536 /** 537 * Vector to matrix multiplication, v1<sup>T</sup> m2. 538 * 539 * @param v1 vector 540 * @param m2 other matrix 541 * @return Matrix product, v1<sup>T</sup> * m2 542 */ transposeTimes(final double[] v1, final double[][] m2)543 public static double[][] transposeTimes(final double[] v1, final double[][] m2) { 544 assert m2.length == v1.length : ERR_MATRIX_INNERDIM; 545 final int columndimension = m2[0].length; 546 final double[][] re = new double[1][columndimension]; 547 for(int j = 0; j < columndimension; j++) { 548 double s = 0; 549 for(int k = 0; k < v1.length; k++) { 550 s += v1[k] * m2[k][j]; 551 } 552 re[0][j] = s; 553 } 554 return re; 555 } 556 557 /** 558 * Vector scalar product (dot product), 559 * v1<sup>T</sup> v2 = v1·v2 = <v1,v2>. 560 * 561 * @param v1 vector 562 * @param v2 other vector 563 * @return scalar result of matrix product, v1<sup>T</sup> * v2 564 */ transposeTimes(final double[] v1, final double[] v2)565 public static double transposeTimes(final double[] v1, final double[] v2) { 566 assert v2.length == v1.length : ERR_VEC_DIMENSIONS; 567 double s = 0; 568 for(int k = 0; k < v1.length; k++) { 569 s += v1[k] * v2[k]; 570 } 571 return s; 572 } 573 574 /** 575 * Vector with transposed matrix multiplication, v1 * m2<sup>T</sup> 576 * (m2 <em>must have one row only</em>). 577 * <p> 578 * Note: this is an unusual operation, m2 must be a costly column matrix. 579 * <p> 580 * This method is equivalent to the 581 * {@link #timesTranspose(double[], double[])} method 582 * with m2 being the second vector as matrix. 583 * 584 * @param v1 vector 585 * @param m2 other matrix 586 * @return Matrix product, v1 * m2<sup>T</sup> 587 * @deprecated this is fairly inefficient memory layout, rewriting your code 588 */ 589 @Deprecated timesTranspose(final double[] v1, final double[][] m2)590 public static double[][] timesTranspose(final double[] v1, final double[][] m2) { 591 assert m2[0].length == 1 : ERR_MATRIX_INNERDIM; 592 593 final double[][] re = new double[v1.length][m2.length]; 594 for(int j = 0; j < m2.length; j++) { 595 for(int i = 0; i < v1.length; i++) { 596 re[i][j] = v1[i] * m2[j][0]; 597 } 598 } 599 return re; 600 } 601 602 /** 603 * Vectors to matrix multiplication, v1 * v2<sup>T</sup>. 604 * 605 * @param v1 vector 606 * @param v2 other vector 607 * @return Matrix product, v1 * v2<sup>T</sup> 608 */ timesTranspose(final double[] v1, final double[] v2)609 public static double[][] timesTranspose(final double[] v1, final double[] v2) { 610 final double[][] re = new double[v1.length][v2.length]; 611 for(int j = 0; j < v2.length; j++) { 612 for(int i = 0; i < v1.length; i++) { 613 re[i][j] = v1[i] * v2[j]; 614 } 615 } 616 return re; 617 } 618 619 /** 620 * Returns the scalar product (dot product) of two vectors, 621 * <v1,v2> = v1<sup>T</sup> v2. 622 * <p> 623 * This is the same as {@link #transposeTimes(double[], double[])}. 624 * 625 * @param v1 vector 626 * @param v2 other vector 627 * @return double the scalar product of vectors v1 and v2 628 */ scalarProduct(final double[] v1, final double[] v2)629 public static double scalarProduct(final double[] v1, final double[] v2) { 630 return transposeTimes(v1, v2); 631 } 632 633 /** 634 * Returns the dot product (scalar product) of two vectors, 635 * v1·v2 = v1<sup>T</sup> v2. 636 * <p> 637 * This is the same as {@link #transposeTimes(double[], double[])}. 638 * 639 * @param v1 vector 640 * @param v2 other vector 641 * @return double the scalar product of vectors v1 and v2 642 */ dot(final double[] v1, final double[] v2)643 public static double dot(final double[] v1, final double[] v2) { 644 return transposeTimes(v1, v2); 645 } 646 647 /** 648 * Sum of the vector components. 649 * 650 * @param v1 vector 651 * @return sum of this vector 652 */ sum(final double[] v1)653 public static double sum(final double[] v1) { 654 double acc = 0.; 655 for(int row = 0; row < v1.length; row++) { 656 acc += v1[row]; 657 } 658 return acc; 659 } 660 661 /** 662 * Squared Euclidean length of the vector v1<sup>T</sup> v1 = v1·v1. 663 * 664 * @param v1 vector 665 * @return squared Euclidean length of this vector 666 */ squareSum(final double[] v1)667 public static double squareSum(final double[] v1) { 668 double acc = 0.0; 669 for(int row = 0; row < v1.length; row++) { 670 final double v = v1[row]; 671 acc += v * v; 672 } 673 return acc; 674 } 675 676 /** 677 * Euclidean length of the vector sqrt(v1<sup>T</sup> v1). 678 * 679 * @param v1 vector 680 * @return Euclidean length of this vector 681 */ euclideanLength(final double[] v1)682 public static double euclideanLength(final double[] v1) { 683 return FastMath.sqrt(squareSum(v1)); 684 } 685 686 /** 687 * Find the maximum value. 688 * 689 * @param v Vector 690 * @return Position of maximum 691 */ argmax(double[] v)692 public static int argmax(double[] v) { 693 assert (v.length > 0); 694 int maxIndex = 0; 695 double currentMax = v[0]; 696 for(int i = 1; i < v.length; i++) { 697 final double x = v[i]; 698 if(x > currentMax) { 699 maxIndex = i; 700 currentMax = x; 701 } 702 } 703 return maxIndex; 704 } 705 706 /** 707 * Normalizes v1 to the length of 1.0. 708 * 709 * @param v1 vector 710 * @return normalized copy of v1 711 */ normalize(final double[] v1)712 public static double[] normalize(final double[] v1) { 713 final double norm = 1. / euclideanLength(v1); 714 double[] re = new double[v1.length]; 715 if(norm < Double.POSITIVE_INFINITY) { 716 for(int row = 0; row < v1.length; row++) { 717 re[row] = v1[row] * norm; 718 } 719 } 720 return re; 721 } 722 723 /** 724 * Normalizes v1 to the length of 1.0 in place. 725 * 726 * @param v1 vector (overwritten) 727 * @return normalized v1 728 */ normalizeEquals(final double[] v1)729 public static double[] normalizeEquals(final double[] v1) { 730 final double norm = 1. / euclideanLength(v1); 731 if(norm < Double.POSITIVE_INFINITY) { 732 for(int row = 0; row < v1.length; row++) { 733 v1[row] *= norm; 734 } 735 } 736 return v1; 737 } 738 739 /** 740 * Compute the hash code for the vector. 741 * 742 * @param v1 elements 743 * @return hash code 744 */ hashCode(final double[] v1)745 public static int hashCode(final double[] v1) { 746 return Arrays.hashCode(v1); 747 } 748 749 /** 750 * Compare for equality. 751 * 752 * @param v1 first vector 753 * @param v2 second vector 754 * @return comparison result 755 */ equals(final double[] v1, final double[] v2)756 public static boolean equals(final double[] v1, final double[] v2) { 757 return Arrays.equals(v1, v2); 758 } 759 760 /** 761 * Reset the vector to 0. 762 * 763 * @param v1 vector 764 */ clear(final double[] v1)765 public static void clear(final double[] v1) { 766 Arrays.fill(v1, 0.0); 767 } 768 769 /** 770 * Reset the matrix to 0. 771 * 772 * @param m Matrix 773 */ clear(final double[][] m)774 public static void clear(final double[][] m) { 775 for(int i = 0; i < m.length; i++) { 776 Arrays.fill(m[i], 0.0); 777 } 778 } 779 780 /** 781 * Rotate the two-dimensional vector by 90 degrees. 782 * 783 * @param v1 first vector 784 * @return modified v1, rotated by 90 degrees 785 */ rotate90Equals(final double[] v1)786 public static double[] rotate90Equals(final double[] v1) { 787 assert v1.length == 2 : "rotate90Equals is only valid for 2d vectors."; 788 final double temp = v1[0]; 789 v1[0] = v1[1]; 790 v1[1] = -temp; 791 return v1; 792 } 793 794 // *********** MATRIX operations 795 796 /** 797 * Returns the unit / identity / "eye" matrix of the specified dimension. 798 * 799 * @param dim the dimensionality of the unit matrix 800 * @return the unit matrix of the specified dimension 801 */ unitMatrix(final int dim)802 public static double[][] unitMatrix(final int dim) { 803 final double[][] e = new double[dim][dim]; 804 for(int i = 0; i < dim; i++) { 805 e[i][i] = 1; 806 } 807 return e; 808 } 809 810 /** 811 * Returns the zero matrix of the specified dimension. 812 * 813 * @param dim the dimensionality of the unit matrix 814 * @return the zero matrix of the specified dimension 815 */ zeroMatrix(final int dim)816 public static double[][] zeroMatrix(final int dim) { 817 return new double[dim][dim]; 818 } 819 820 /** 821 * Generate unit / identity / "eye" matrix. 822 * 823 * @param m Number of rows. 824 * @param n Number of columns. 825 * @return An m-by-n matrix with ones on the diagonal and zeros elsewhere. 826 */ identity(final int m, final int n)827 public static double[][] identity(final int m, final int n) { 828 final double[][] A = new double[m][n]; 829 final int dim = m < n ? m : n; 830 for(int i = 0; i < dim; i++) { 831 A[i][i] = 1.0; 832 } 833 return A; 834 } 835 836 /** 837 * Returns a quadratic matrix consisting of zeros and of the given values on 838 * the diagonal. 839 * 840 * @param v1 the values on the diagonal 841 * @return the resulting matrix 842 */ 843 public static double[][] diagonal(final double[] v1) { 844 final int dim = v1.length; 845 final double[][] result = new double[dim][dim]; 846 for(int i = 0; i < dim; i++) { 847 result[i][i] = v1[i]; 848 } 849 return result; 850 } 851 852 /** 853 * Make a deep copy of a matrix. 854 * 855 * @param m1 Input matrix 856 * @return a new matrix containing the same values as this matrix 857 */ 858 public static double[][] copy(final double[][] m1) { 859 final int rowdim = m1.length, coldim = getColumnDimensionality(m1); 860 final double[][] X = new double[rowdim][coldim]; 861 for(int i = 0; i < rowdim; i++) { 862 System.arraycopy(m1[i], 0, X[i], 0, coldim); 863 } 864 return X; 865 } 866 867 /** 868 * Make a one-dimensional row packed copy of the internal array. 869 * 870 * @param m1 Input matrix 871 * @return Matrix elements packed in a one-dimensional array by rows. 872 */ 873 public static double[] rowPackedCopy(final double[][] m1) { 874 final int rowdim = m1.length, coldim = getColumnDimensionality(m1); 875 final double[] vals = new double[rowdim * coldim]; 876 for(int i = 0, j = 0; i < rowdim; i++, j += coldim) { 877 // assert m1[i].length == coldim : ERR_MATRIX_RAGGED; 878 System.arraycopy(m1[i], 0, vals, j, coldim); 879 } 880 return vals; 881 } 882 883 /** 884 * Make a one-dimensional column packed copy of the internal array. 885 * 886 * @param m1 Input matrix 887 * @return Matrix elements packed in a one-dimensional array by columns. 888 */ 889 public static double[] columnPackedCopy(final double[][] m1) { 890 final int rowdim = m1.length, coldim = getColumnDimensionality(m1); 891 final double[] vals = new double[m1.length * coldim]; 892 for(int i = 0; i < rowdim; i++) { 893 final double[] rowM = m1[i]; 894 // assert rowM.length == coldim : ERR_MATRIX_RAGGED; 895 for(int j = 0, k = i; j < coldim; j++, k += rowdim) { 896 vals[k] = rowM[j]; 897 } 898 } 899 return vals; 900 } 901 902 /** 903 * Get a submatrix. 904 * 905 * @param m1 Input matrix 906 * @param r0 Initial row index 907 * @param r1 Final row index (exclusive) 908 * @param c0 Initial column index 909 * @param c1 Final column index (exclusive) 910 * @return m1(r0:r1-1,c0:c1-1) 911 */ 912 public static double[][] getMatrix(final double[][] m1, final int r0, final int r1, final int c0, final int c1) { 913 assert r0 <= r1 && c0 <= c1 : ERR_INVALID_RANGE; 914 assert r1 <= m1.length && c1 <= m1[0].length : ERR_MATRIX_DIMENSIONS; 915 final int rowdim = r1 - r0, coldim = c1 - c0; 916 final double[][] X = new double[rowdim][coldim]; 917 for(int i = r0; i < r1; i++) { 918 System.arraycopy(m1[i], c0, X[i - r0], 0, coldim); 919 } 920 return X; 921 } 922 923 /** 924 * Get a submatrix. 925 * 926 * @param m1 Input matrix 927 * @param r Array of row indices. 928 * @param c Array of column indices. 929 * @return m1(r(:),c(:)) 930 */ 931 public static double[][] getMatrix(final double[][] m1, final int[] r, final int[] c) { 932 final int rowdim = r.length, coldim = c.length; 933 final double[][] X = new double[rowdim][coldim]; 934 for(int i = 0; i < rowdim; i++) { 935 final double[] rowM = m1[r[i]], rowX = X[i]; 936 for(int j = 0; j < coldim; j++) { 937 rowX[j] = rowM[c[j]]; 938 } 939 } 940 return X; 941 } 942 943 /** 944 * Get a submatrix. 945 * 946 * @param m1 Input matrix 947 * @param r Array of row indices. 948 * @param c0 Initial column index 949 * @param c1 Final column index (exclusive) 950 * @return m1(r(:),c0:c1-1) 951 */ 952 public static double[][] getMatrix(final double[][] m1, final int[] r, final int c0, final int c1) { 953 assert c0 <= c1 : ERR_INVALID_RANGE; 954 assert c1 <= m1[0].length : ERR_MATRIX_DIMENSIONS; 955 final int rowdim = r.length, coldim = c1 - c0; 956 final double[][] X = new double[rowdim][coldim]; 957 for(int i = 0; i < rowdim; i++) { 958 System.arraycopy(m1[r[i]], c0, X[i], 0, coldim); 959 } 960 return X; 961 } 962 963 /** 964 * Get a submatrix. 965 * 966 * @param m1 Input matrix 967 * @param r0 Initial row index 968 * @param r1 Final row index (exclusive) 969 * @param c Array of column indices. 970 * @return m1(r0:r1-1,c(:)) 971 */ 972 public static double[][] getMatrix(final double[][] m1, final int r0, final int r1, final int[] c) { 973 assert r0 <= r1 : ERR_INVALID_RANGE; 974 assert r1 <= m1.length : ERR_MATRIX_DIMENSIONS; 975 final int rowdim = r1 - r0, coldim = c.length; 976 final double[][] X = new double[rowdim][coldim]; 977 for(int i = r0; i < r1; i++) { 978 final double[] row = m1[i]; 979 final double[] Xi = X[i - r0]; 980 for(int j = 0; j < coldim; j++) { 981 Xi[j] = row[c[j]]; 982 } 983 } 984 return X; 985 } 986 987 /** 988 * Set a submatrix. 989 * 990 * @param m1 Original matrix 991 * @param r0 Initial row index 992 * @param r1 Final row index (exclusive) 993 * @param c0 Initial column index 994 * @param c1 Final column index (exclusive) 995 * @param m2 New values for m1(r0:r1-1,c0:c1-1) 996 */ 997 public static void setMatrix(final double[][] m1, final int r0, final int r1, final int c0, final int c1, final double[][] m2) { 998 assert r0 <= r1 && c0 <= c1 : ERR_INVALID_RANGE; 999 assert r1 <= m1.length && c1 <= m1[0].length : ERR_MATRIX_DIMENSIONS; 1000 final int coldim = c1 - c0; 1001 for(int i = r0; i < r1; i++) { 1002 System.arraycopy(m2[i - r0], 0, m1[i], c0, coldim); 1003 } 1004 } 1005 1006 /** 1007 * Set a submatrix. 1008 * 1009 * @param m1 Original matrix 1010 * @param r Array of row indices. 1011 * @param c Array of column indices. 1012 * @param m2 New values for m1(r(:),c(:)) 1013 */ 1014 public static void setMatrix(final double[][] m1, final int[] r, final int[] c, final double[][] m2) { 1015 for(int i = 0; i < r.length; i++) { 1016 final double[] row1 = m1[r[i]], row2 = m2[i]; 1017 for(int j = 0; j < c.length; j++) { 1018 row1[c[j]] = row2[j]; 1019 } 1020 } 1021 } 1022 1023 /** 1024 * Set a submatrix. 1025 * 1026 * @param m1 Input matrix 1027 * @param r Array of row indices. 1028 * @param c0 Initial column index 1029 * @param c1 Final column index (exclusive) 1030 * @param m2 New values for m1(r(:),c0:c1-1) 1031 */ 1032 public static void setMatrix(final double[][] m1, final int[] r, final int c0, final int c1, final double[][] m2) { 1033 assert c0 <= c1 : ERR_INVALID_RANGE; 1034 assert c1 <= m1[0].length : ERR_MATRIX_DIMENSIONS; 1035 for(int i = 0; i < r.length; i++) { 1036 System.arraycopy(m2[i], 0, m1[r[i]], c0, c1 - c0); 1037 } 1038 } 1039 1040 /** 1041 * Set a submatrix. 1042 * 1043 * @param m1 Input matrix 1044 * @param r0 Initial row index 1045 * @param r1 Final row index 1046 * @param c Array of column indices. 1047 * @param m2 New values for m1(r0:r1-1,c(:)) 1048 */ 1049 public static void setMatrix(final double[][] m1, final int r0, final int r1, final int[] c, final double[][] m2) { 1050 assert r0 <= r1 : ERR_INVALID_RANGE; 1051 assert r1 <= m1.length : ERR_MATRIX_DIMENSIONS; 1052 for(int i = r0; i < r1; i++) { 1053 final double[] row1 = m1[i], row2 = m2[i - r0]; 1054 for(int j = 0; j < c.length; j++) { 1055 row1[c[j]] = row2[j]; 1056 } 1057 } 1058 } 1059 1060 /** 1061 * Returns the <code>r</code>th row of this matrix as vector. 1062 * 1063 * @param m1 Input matrix 1064 * @param r the index of the row to be returned 1065 * @return the <code>r</code>th row of this matrix 1066 */ 1067 public static double[] getRow(final double[][] m1, final int r) { 1068 return m1[r].clone(); 1069 } 1070 1071 /** 1072 * Sets the <code>r</code>th row of this matrix to the specified vector. 1073 * 1074 * @param m1 Original matrix 1075 * @param r the index of the column to be set 1076 * @param row the value of the column to be set 1077 */ 1078 public static void setRow(final double[][] m1, final int r, final double[] row) { 1079 final int columndimension = getColumnDimensionality(m1); 1080 assert row.length == columndimension : ERR_DIMENSIONS; 1081 System.arraycopy(row, 0, m1[r], 0, columndimension); 1082 } 1083 1084 /** 1085 * Get a column from a matrix as vector. 1086 * 1087 * @param m1 Matrix to extract the column from 1088 * @param col Column number 1089 * @return Column 1090 */ 1091 public static double[] getCol(double[][] m1, int col) { 1092 double[] ret = new double[m1.length]; 1093 for(int i = 0; i < ret.length; i++) { 1094 ret[i] = m1[i][col]; 1095 } 1096 return ret; 1097 } 1098 1099 /** 1100 * Sets the <code>c</code>th column of this matrix to the specified column. 1101 * 1102 * @param m1 Input matrix 1103 * @param c the index of the column to be set 1104 * @param column the value of the column to be set 1105 */ 1106 public static void setCol(final double[][] m1, final int c, final double[] column) { 1107 assert column.length == m1.length : ERR_DIMENSIONS; 1108 for(int i = 0; i < m1.length; i++) { 1109 m1[i][c] = column[i]; 1110 } 1111 } 1112 1113 /** 1114 * Matrix transpose 1115 * 1116 * @param m1 Input matrix 1117 * @return m1<sup>T</sup> as copy 1118 */ 1119 public static double[][] transpose(final double[][] m1) { 1120 final int rowdim = m1.length, coldim = getColumnDimensionality(m1); 1121 final double[][] re = new double[coldim][rowdim]; 1122 for(int i = 0; i < rowdim; i++) { 1123 final double[] row = m1[i]; 1124 for(int j = 0; j < coldim; j++) { 1125 re[j][i] = row[j]; 1126 } 1127 } 1128 return re; 1129 } 1130 1131 /** 1132 * Component-wise matrix sum: m3 = m1 + m2. 1133 * 1134 * @param m1 Input matrix 1135 * @param m2 another matrix 1136 * @return m1 + m1 in a new Matrix 1137 */ 1138 public static double[][] plus(final double[][] m1, final double[][] m2) { 1139 return plusEquals(copy(m1), m2); 1140 } 1141 1142 /** 1143 * Component-wise matrix operation: m3 = m1 + m2 * s2. 1144 * 1145 * @param m1 Input matrix 1146 * @param m2 another matrix 1147 * @param s2 scalar 1148 * @return m1 + m2 * s2 in a new matrix 1149 */ 1150 public static double[][] plusTimes(final double[][] m1, final double[][] m2, final double s2) { 1151 return plusTimesEquals(copy(m1), m2, s2); 1152 } 1153 1154 /** 1155 * Component-wise matrix operation: m1 = m1 + m2, 1156 * overwriting the existing matrix m1. 1157 * 1158 * @param m1 input matrix (overwritten) 1159 * @param m2 another matrix 1160 * @return m1 = m1 + m2 1161 */ 1162 public static double[][] plusEquals(final double[][] m1, final double[][] m2) { 1163 final int rowdim = m1.length, coldim = getColumnDimensionality(m1); 1164 assert getRowDimensionality(m1) == getRowDimensionality(m2) && coldim == getColumnDimensionality(m2) : ERR_MATRIX_DIMENSIONS; 1165 for(int i = 0; i < rowdim; i++) { 1166 final double[] row1 = m1[i], row2 = m2[i]; 1167 for(int j = 0; j < coldim; j++) { 1168 row1[j] += row2[j]; 1169 } 1170 } 1171 return m1; 1172 } 1173 1174 /** 1175 * Component-wise matrix operation: m1 = m1 + m2 * s2, 1176 * overwriting the existing matrix m1. 1177 * 1178 * @param m1 input matrix (overwritten) 1179 * @param m2 another matrix 1180 * @param s2 scalar for s2 1181 * @return m1 = m1 + m2 * s2, overwriting m1 1182 */ 1183 public static double[][] plusTimesEquals(final double[][] m1, final double[][] m2, final double s2) { 1184 final int rowdim = m1.length, coldim = getColumnDimensionality(m1); 1185 assert getRowDimensionality(m1) == getRowDimensionality(m2) && coldim == getColumnDimensionality(m2) : ERR_MATRIX_DIMENSIONS; 1186 for(int i = 0; i < rowdim; i++) { 1187 final double[] row1 = m1[i], row2 = m2[i]; 1188 for(int j = 0; j < coldim; j++) { 1189 row1[j] += s2 * row2[j]; 1190 } 1191 } 1192 return m1; 1193 } 1194 1195 /** 1196 * Component-wise matrix subtraction m3 = m1 - m2. 1197 * 1198 * @param m1 Input matrix 1199 * @param m2 another matrix 1200 * @return m1 - m2 in a new matrix 1201 */ 1202 public static double[][] minus(final double[][] m1, final double[][] m2) { 1203 return minusEquals(copy(m1), m2); 1204 } 1205 1206 /** 1207 * Component-wise matrix operation: m3 = m1 - m2 * s2 1208 * 1209 * @param m1 Input matrix 1210 * @param m2 another matrix 1211 * @param s2 Scalar 1212 * @return m1 - m2 * s2 in a new Matrix 1213 */ 1214 public static double[][] minusTimes(final double[][] m1, final double[][] m2, final double s2) { 1215 return minusTimesEquals(copy(m1), m2, s2); 1216 } 1217 1218 /** 1219 * Component-wise matrix subtraction: m1 = m1 - m2, 1220 * overwriting the existing matrix m1. 1221 * 1222 * @param m1 Input matrix 1223 * @param m2 another matrix 1224 * @return m1 - m2, overwriting m1 1225 */ 1226 public static double[][] minusEquals(final double[][] m1, final double[][] m2) { 1227 final int columndimension = getColumnDimensionality(m1); 1228 assert getRowDimensionality(m1) == getRowDimensionality(m2) && columndimension == getColumnDimensionality(m2) : ERR_MATRIX_DIMENSIONS; 1229 for(int i = 0; i < m1.length; i++) { 1230 final double[] row1 = m1[i], row2 = m2[i]; 1231 for(int j = 0; j < columndimension; j++) { 1232 row1[j] -= row2[j]; 1233 } 1234 } 1235 return m1; 1236 } 1237 1238 /** 1239 * Component-wise matrix operation: m1 = m1 - m2 * s2, 1240 * overwriting the existing matrix m1. 1241 * 1242 * @param m1 Input matrix 1243 * @param m2 another matrix 1244 * @param s2 Scalar 1245 * @return m1 = m1 - s2 * m2, overwriting m1 1246 */ 1247 public static double[][] minusTimesEquals(final double[][] m1, final double[][] m2, final double s2) { 1248 assert getRowDimensionality(m1) == getRowDimensionality(m2) && getColumnDimensionality(m1) == getColumnDimensionality(m2) : ERR_MATRIX_DIMENSIONS; 1249 for(int i = 0; i < m1.length; i++) { 1250 final double[] row1 = m1[i], row2 = m2[i]; 1251 for(int j = 0; j < row1.length; j++) { 1252 row1[j] -= s2 * row2[j]; 1253 } 1254 } 1255 return m1; 1256 } 1257 1258 /** 1259 * Multiply a matrix by a scalar component-wise, m3 = m1 * s1. 1260 * 1261 * @param m1 Input matrix 1262 * @param s1 scalar 1263 * @return m1 * s1, in a new matrix 1264 */ 1265 public static double[][] times(final double[][] m1, final double s1) { 1266 return timesEquals(copy(m1), s1); 1267 } 1268 1269 /** 1270 * Multiply a matrix by a scalar component-wise in place, m1 = m1 * s1, 1271 * overwriting the existing matrix m1. 1272 * 1273 * @param m1 Input matrix 1274 * @param s1 scalar 1275 * @return m1 = m1 * s1, overwriting m1 1276 */ 1277 public static double[][] timesEquals(final double[][] m1, final double s1) { 1278 final int rowdim = m1.length; 1279 for(int i = 0; i < rowdim; i++) { 1280 final double[] row = m1[i]; 1281 for(int j = 0; j < row.length; j++) { 1282 row[j] *= s1; 1283 } 1284 } 1285 return m1; 1286 } 1287 1288 /** 1289 * Matrix multiplication, m1 * m2. 1290 * 1291 * @param m1 Input matrix 1292 * @param m2 another matrix 1293 * @return Matrix product, m1 * m2 1294 */ 1295 public static double[][] times(final double[][] m1, final double[][] m2) { 1296 final int rowdim1 = m1.length, coldim1 = getColumnDimensionality(m1); 1297 final int coldim2 = getColumnDimensionality(m2); 1298 // Optimized implementation, exploiting the storage layout 1299 assert m2.length == coldim1 : ERR_MATRIX_INNERDIM; 1300 final double[][] r2 = new double[rowdim1][coldim2]; 1301 // Optimized ala Jama. jik order. 1302 final double[] Bcolj = new double[coldim1]; 1303 for(int j = 0; j < coldim2; j++) { 1304 // Make a linear copy of column j from B 1305 for(int k = 0; k < coldim1; k++) { 1306 Bcolj[k] = m2[k][j]; 1307 } 1308 // multiply it with each row from A 1309 for(int i = 0; i < rowdim1; i++) { 1310 final double[] Arowi = m1[i]; 1311 double s = 0; 1312 for(int k = 0; k < coldim1; k++) { 1313 s += Arowi[k] * Bcolj[k]; 1314 } 1315 r2[i][j] = s; 1316 } 1317 } 1318 return r2; 1319 } 1320 1321 /** 1322 * Matrix with vector multiplication, m1 * v2. 1323 * 1324 * @param m1 Input matrix 1325 * @param v2 a vector 1326 * @return Matrix product, m1 * v2 1327 */ 1328 public static double[] times(final double[][] m1, final double[] v2) { 1329 final int rowdim = m1.length, coldim = getColumnDimensionality(m1); 1330 assert v2.length == coldim : ERR_MATRIX_INNERDIM; 1331 final double[] re = new double[rowdim]; 1332 // multiply it with each row from A 1333 for(int i = 0; i < rowdim; i++) { 1334 final double[] Arowi = m1[i]; 1335 // assert Arowi.length == coldim : ERR_MATRIX_RAGGED; 1336 double s = 0; 1337 for(int k = 0; k < coldim; k++) { 1338 s += Arowi[k] * v2[k]; 1339 } 1340 re[i] = s; 1341 } 1342 return re; 1343 } 1344 1345 /** 1346 * Transposed matrix with vector multiplication, m1<sup>T</sup> * v2 1347 * 1348 * @param m1 Input matrix 1349 * @param v2 another matrix 1350 * @return Matrix product, m1<sup>T</sup> * v2 1351 */ 1352 public static double[] transposeTimes(final double[][] m1, final double[] v2) { 1353 final int rowdim = m1.length, coldim = getColumnDimensionality(m1); 1354 assert v2.length == rowdim : ERR_MATRIX_INNERDIM; 1355 final double[] re = new double[coldim]; 1356 // multiply it with each row from A 1357 for(int i = 0; i < coldim; i++) { 1358 double s = 0; 1359 for(int k = 0; k < rowdim; k++) { 1360 s += m1[k][i] * v2[k]; 1361 } 1362 re[i] = s; 1363 } 1364 return re; 1365 } 1366 1367 /** 1368 * Matrix multiplication, m1<sup>T</sup> * m2 1369 * 1370 * @param m1 Input matrix 1371 * @param m2 another matrix 1372 * @return Matrix product, m1<sup>T</sup> * m2 1373 */ 1374 public static double[][] transposeTimes(final double[][] m1, final double[][] m2) { 1375 final int rowdim1 = m1.length, coldim1 = getColumnDimensionality(m1); 1376 final int coldim2 = getColumnDimensionality(m2); 1377 assert m2.length == rowdim1 : ERR_MATRIX_INNERDIM; 1378 final double[][] re = new double[coldim1][coldim2]; 1379 final double[] Bcolj = new double[rowdim1]; 1380 for(int j = 0; j < coldim2; j++) { 1381 // Make a linear copy of column j from B 1382 for(int k = 0; k < rowdim1; k++) { 1383 Bcolj[k] = m2[k][j]; 1384 } 1385 // multiply it with each row from A 1386 for(int i = 0; i < coldim1; i++) { 1387 double s = 0; 1388 for(int k = 0; k < rowdim1; k++) { 1389 s += m1[k][i] * Bcolj[k]; 1390 } 1391 re[i][j] = s; 1392 } 1393 } 1394 return re; 1395 } 1396 1397 /** 1398 * Matrix multiplication, v1<sup>T</sup> * m2 * v3 1399 * 1400 * @param v1 vector on the left 1401 * @param m2 matrix 1402 * @param v3 vector on the right 1403 * @return Matrix product, v1<sup>T</sup> * m2 * v3 1404 */ 1405 public static double transposeTimesTimes(final double[] v1, final double[][] m2, final double[] v3) { 1406 final int rowdim = m2.length, coldim = getColumnDimensionality(m2); 1407 assert rowdim == v1.length : ERR_MATRIX_INNERDIM; 1408 assert coldim == v3.length : ERR_MATRIX_INNERDIM; 1409 double sum = 0.0; 1410 for(int k = 0; k < rowdim; k++) { 1411 final double[] B_k = m2[k]; 1412 double s = 0; 1413 for(int j = 0; j < coldim; j++) { 1414 s += v3[j] * B_k[j]; 1415 } 1416 sum += s * v1[k]; 1417 } 1418 return sum; 1419 } 1420 1421 /** 1422 * Matrix multiplication, m1 * m2<sup>T</sup> 1423 * 1424 * @param m1 Input matrix 1425 * @param m2 another matrix 1426 * @return Matrix product, m1 * m2<sup>T</sup> 1427 */ 1428 public static double[][] timesTranspose(final double[][] m1, final double[][] m2) { 1429 final int rowdim1 = m1.length, coldim1 = getColumnDimensionality(m1); 1430 final int rowdim2 = m2.length; 1431 assert coldim1 == getColumnDimensionality(m2) : ERR_MATRIX_INNERDIM; 1432 final double[][] re = new double[rowdim1][rowdim2]; 1433 for(int j = 0; j < rowdim2; j++) { 1434 final double[] Browj = m2[j]; 1435 // multiply it with each row from A 1436 for(int i = 0; i < rowdim1; i++) { 1437 final double[] Arowi = m1[i]; 1438 double s = 0; 1439 // assert Arowi.length == coldim1 : ERR_MATRIX_RAGGED; 1440 // assert Browj.length == coldim1 : ERR_MATRIX_INNERDIM; 1441 for(int k = 0; k < coldim1; k++) { 1442 s += Arowi[k] * Browj[k]; 1443 } 1444 re[i][j] = s; 1445 } 1446 } 1447 return re; 1448 } 1449 1450 /** 1451 * Matrix multiplication, m1<sup>T</sup> * m2<sup>T</sup>. 1452 * Computed as (m2*m1)<sup>T</sup> 1453 * 1454 * @param m1 Input matrix 1455 * @param m2 another matrix 1456 * @return Matrix product, m1<sup>T</sup> * m2<sup>T</sup> 1457 */ 1458 public static double[][] transposeTimesTranspose(final double[][] m1, final double[][] m2) { 1459 // Optimized implementation, exploiting the storage layout 1460 assert m1.length == getColumnDimensionality(m2) : ERR_MATRIX_INNERDIM; 1461 final double[][] re = new double[getColumnDimensionality(m1)][m2.length]; 1462 // Optimized ala Jama. jik order. 1463 final double[] Acolj = new double[m1.length]; 1464 for(int j = 0; j < re.length; j++) { 1465 // Make a linear copy of column j from A 1466 for(int k = 0; k < m1.length; k++) { 1467 Acolj[k] = m1[k][j]; 1468 } 1469 final double[] Xrow = re[j]; 1470 // multiply it with each row from A 1471 for(int i = 0; i < m2.length; i++) { 1472 final double[] Browi = m2[i]; 1473 double s = 0; 1474 for(int k = 0; k < m1.length; k++) { 1475 s += Browi[k] * Acolj[k]; 1476 } 1477 Xrow[i] = s; 1478 } 1479 } 1480 return re; 1481 } 1482 1483 /** 1484 * Matrix multiplication with diagonal, m1^T * d2 * m3 1485 * 1486 * @param m1 Left matrix 1487 * @param d2 Diagonal entries 1488 * @param m3 Right matrix 1489 * @return m1^T * d2 * m3 1490 */ 1491 public static double[][] transposeDiagonalTimes(double[][] m1, double[] d2, double[][] m3) { 1492 final int innerdim = d2.length; 1493 assert m1.length == innerdim : ERR_MATRIX_INNERDIM; 1494 assert m3.length == innerdim : ERR_MATRIX_INNERDIM; 1495 final int coldim1 = getColumnDimensionality(m1); 1496 final int coldim2 = getColumnDimensionality(m3); 1497 final double[][] r = new double[coldim1][coldim2]; 1498 final double[] Acoli = new double[innerdim]; // Buffer 1499 // multiply it with each row from A 1500 for(int i = 0; i < coldim1; i++) { 1501 final double[] r_i = r[i]; // Output row 1502 // Make a linear copy of column i from A 1503 for(int k = 0; k < innerdim; k++) { 1504 Acoli[k] = m1[k][i] * d2[k]; 1505 } 1506 for(int j = 0; j < coldim2; j++) { 1507 double s = 0; 1508 for(int k = 0; k < innerdim; k++) { 1509 s += Acoli[k] * m3[k][j]; 1510 } 1511 r_i[j] = s; 1512 } 1513 } 1514 return r; 1515 } 1516 1517 /** 1518 * Matrix multiplication, (a-c)<sup>T</sup> * B * (a-c) 1519 * <p> 1520 * Note: it may (or may not) be more efficient to materialize (a-c), then use 1521 * {@code transposeTimesTimes(a_minus_c, B, a_minus_c)} instead. 1522 * 1523 * @param B matrix 1524 * @param a First vector 1525 * @param c Center vector 1526 * @return Matrix product, (a-c)<sup>T</sup> * B * (a-c) 1527 */ 1528 @Reference(authors = "P. C. Mahalanobis", // 1529 title = "On the generalized distance in statistics", // 1530 booktitle = "Proceedings of the National Institute of Sciences of India. 2 (1)", // 1531 bibkey = "journals/misc/Mahalanobis36") 1532 public static double mahalanobisDistance(final double[][] B, final double[] a, final double[] c) { 1533 final int rowdim = B.length, coldim = getColumnDimensionality(B); 1534 assert rowdim == a.length : ERR_MATRIX_INNERDIM; 1535 assert coldim == c.length : ERR_MATRIX_INNERDIM; 1536 assert a.length == c.length : ERR_VEC_DIMENSIONS; 1537 double sum = 0.0; 1538 for(int k = 0; k < rowdim; k++) { 1539 final double[] B_k = B[k]; 1540 double s = 0; 1541 for(int j = 0; j < coldim; j++) { 1542 s += (a[j] - c[j]) * B_k[j]; 1543 } 1544 sum += (a[k] - c[k]) * s; 1545 } 1546 return sum; 1547 } 1548 1549 /** 1550 * getDiagonal returns array of diagonal-elements. 1551 * 1552 * @param m1 Input matrix 1553 * @return values on the diagonal of the Matrix 1554 */ 1555 public static double[] getDiagonal(final double[][] m1) { 1556 final int dim = Math.min(getColumnDimensionality(m1), m1.length); 1557 final double[] diagonal = new double[dim]; 1558 for(int i = 0; i < dim; i++) { 1559 diagonal[i] = m1[i][i]; 1560 } 1561 return diagonal; 1562 } 1563 1564 /** 1565 * Normalizes the columns of this matrix to length of 1.0. 1566 * 1567 * Note: if a column has length 0, it will remain unmodified. 1568 * 1569 * @param m1 Input matrix 1570 */ 1571 public static void normalizeColumns(final double[][] m1) { 1572 final int columndimension = getColumnDimensionality(m1); 1573 for(int col = 0; col < columndimension; col++) { 1574 double norm = 0.0; 1575 for(int row = 0; row < m1.length; row++) { 1576 final double v = m1[row][col]; 1577 norm += v * v; 1578 } 1579 if(norm > 0) { 1580 norm = FastMath.sqrt(norm); 1581 for(int row = 0; row < m1.length; row++) { 1582 m1[row][col] /= norm; 1583 } 1584 } 1585 } 1586 } 1587 1588 /** 1589 * Returns a matrix which consists of this matrix and the specified columns. 1590 * 1591 * @param m1 Input matrix 1592 * @param m2 the columns to be appended 1593 * @return the new matrix with the appended columns 1594 */ 1595 public static double[][] appendColumns(final double[][] m1, final double[][] m2) { 1596 final int columndimension = getColumnDimensionality(m1); 1597 final int ccolumndimension = getColumnDimensionality(m2); 1598 assert m1.length == m2.length : "m.getRowDimension() != column.getRowDimension()"; 1599 1600 final int rcolumndimension = columndimension + ccolumndimension; 1601 final double[][] result = new double[m1.length][rcolumndimension]; 1602 for(int i = 0; i < rcolumndimension; i++) { 1603 // FIXME: optimize - excess copying! 1604 if(i < columndimension) { 1605 setCol(result, i, getCol(m1, i)); 1606 } 1607 else { 1608 setCol(result, i, getCol(m2, i - columndimension)); 1609 } 1610 } 1611 return result; 1612 } 1613 1614 /** 1615 * Returns an orthonormalization of this matrix. 1616 * 1617 * @param m1 Input matrix 1618 * @return the orthonormalized matrix 1619 */ 1620 public static double[][] orthonormalize(final double[][] m1) { 1621 final int columndimension = getColumnDimensionality(m1); 1622 final double[][] v = copy(m1); 1623 1624 // FIXME: optimize - excess copying! 1625 for(int i = 1; i < columndimension; i++) { 1626 final double[] u_i = getCol(m1, i); 1627 final double[] sum = new double[m1.length]; 1628 for(int j = 0; j < i; j++) { 1629 final double[] v_j = getCol(v, j); 1630 final double scalar = scalarProduct(u_i, v_j) / scalarProduct(v_j, v_j); 1631 plusEquals(sum, times(v_j, scalar)); 1632 } 1633 final double[] v_i = minus(u_i, sum); 1634 setCol(v, i, v_i); 1635 } 1636 1637 normalizeColumns(v); 1638 return v; 1639 } 1640 1641 /** 1642 * Solve A*X = B 1643 * 1644 * @param B right hand side 1645 * @return solution if A is square, least squares solution otherwise 1646 */ 1647 public static double[][] solve(double[][] A, double[][] B) { 1648 final int rows = A.length, cols = A[0].length; 1649 return rows == cols // 1650 ? (new LUDecomposition(A, rows, cols)).solve(B) // 1651 : (new QRDecomposition(A, rows, cols)).solve(B); 1652 } 1653 1654 /** 1655 * Solve A*X = b 1656 * 1657 * @param b right hand side 1658 * @return solution if A is square, least squares solution otherwise 1659 */ 1660 public static double[] solve(double[][] A, double[] b) { 1661 final int rows = A.length, cols = A[0].length; 1662 return rows == cols // 1663 ? (new LUDecomposition(A, rows, cols)).solve(b) // 1664 : (new QRDecomposition(A, rows, cols)).solve(b); 1665 } 1666 1667 /** 1668 * Matrix inverse or pseudoinverse 1669 * 1670 * @param A matrix to invert 1671 * @return inverse(A) if A is square, pseudoinverse otherwise. 1672 */ 1673 public static double[][] inverse(double[][] A) { 1674 final int rows = A.length, cols = A[0].length; 1675 return rows == cols // 1676 ? (new LUDecomposition(A, rows, cols)).inverse() // 1677 : (new QRDecomposition(A, rows, cols)).inverse(); 1678 } 1679 1680 /** 1681 * Frobenius norm 1682 * 1683 * @param elements Matrix 1684 * @return sqrt of sum of squares of all elements. 1685 */ 1686 public static double normF(double[][] elements) { 1687 double f = 0; 1688 for(int i = 0; i < elements.length; i++) { 1689 final double[] row = elements[i]; 1690 for(int j = 0; j < row.length; j++) { 1691 final double v = row[j]; 1692 f += v * v; 1693 } 1694 } 1695 // TODO: detect overflow, fall back to slower hypot() 1696 return FastMath.sqrt(f); 1697 } 1698 1699 /** 1700 * Compute hash code 1701 * 1702 * @param m1 Input matrix 1703 * @return Hash code 1704 */ 1705 public static int hashCode(final double[][] m1) { 1706 return Arrays.deepHashCode(m1); 1707 } 1708 1709 /** 1710 * Test for equality 1711 * 1712 * @param m1 Input matrix 1713 * @param m2 Other matrix 1714 * @return Equality 1715 */ 1716 public static boolean equals(final double[][] m1, final double[][] m2) { 1717 return Arrays.deepEquals(m1, m2); 1718 } 1719 1720 /** 1721 * Compare two matrices with a delta parameter to take numerical errors into 1722 * account. 1723 * 1724 * @param m1 Input matrix 1725 * @param m2 other matrix to compare with 1726 * @param maxdelta maximum delta allowed 1727 * @return true if delta smaller than maximum 1728 */ 1729 public static boolean almostEquals(final double[][] m1, final double[][] m2, final double maxdelta) { 1730 if(m1 == m2) { 1731 return true; 1732 } 1733 if(m1 == null || m2 == null) { 1734 return false; 1735 } 1736 final int rowdim = m1.length, coldim = getColumnDimensionality(m1); 1737 if(rowdim != m2.length || coldim != getColumnDimensionality(m2)) { 1738 return false; 1739 } 1740 for(int i = 0; i < rowdim; i++) { 1741 for(int j = 0; j < coldim; j++) { 1742 if(Math.abs(m1[i][j] - m2[i][j]) > maxdelta) { 1743 return false; 1744 } 1745 } 1746 } 1747 return true; 1748 } 1749 1750 /** 1751 * Compare two matrices with a delta parameter to take numerical errors into 1752 * account. 1753 * 1754 * @param m1 Input matrix 1755 * @param m2 other matrix to compare with 1756 * @return almost equals with delta {@link #DELTA} 1757 */ 1758 public static boolean almostEquals(final double[][] m1, final double[][] m2) { 1759 return almostEquals(m1, m2, DELTA); 1760 } 1761 1762 /** 1763 * Compare two matrices with a delta parameter to take numerical errors into 1764 * account. 1765 * 1766 * @param m1 Input matrix 1767 * @param m2 other matrix to compare with 1768 * @param maxdelta maximum delta allowed 1769 * @return true if delta smaller than maximum 1770 */ 1771 public static boolean almostEquals(final double[] m1, final double[] m2, final double maxdelta) { 1772 if(m1 == m2) { 1773 return true; 1774 } 1775 if(m1 == null || m2 == null) { 1776 return false; 1777 } 1778 final int rowdim = m1.length; 1779 if(rowdim != m2.length) { 1780 return false; 1781 } 1782 for(int i = 0; i < rowdim; i++) { 1783 if(Math.abs(m1[i] - m2[i]) > maxdelta) { 1784 return false; 1785 } 1786 } 1787 return true; 1788 } 1789 1790 /** 1791 * Compare two matrices with a delta parameter to take numerical errors into 1792 * account. 1793 * 1794 * @param m1 Input matrix 1795 * @param m2 other matrix to compare with 1796 * @return almost equals with delta {@link #DELTA} 1797 */ 1798 public static boolean almostEquals(final double[] m1, final double[] m2) { 1799 return almostEquals(m1, m2, DELTA); 1800 } 1801 1802 /** 1803 * Returns the dimensionality of the rows of this matrix. 1804 * 1805 * @param m1 Input matrix 1806 * @return the number of rows. 1807 */ 1808 public static int getRowDimensionality(final double[][] m1) { 1809 return m1.length; 1810 } 1811 1812 /** 1813 * Returns the dimensionality of the columns of this matrix. 1814 * 1815 * @param m1 Input matrix 1816 * @return the number of columns. 1817 */ 1818 public static int getColumnDimensionality(final double[][] m1) { 1819 return m1[0].length; 1820 } 1821 1822 /** 1823 * Compute the cosine of the angle between two vectors, 1824 * where the smaller angle between those vectors is viewed. 1825 * 1826 * @param v1 first vector 1827 * @param v2 second vector 1828 * @return cosine of the smaller angle 1829 */ 1830 public static double angle(double[] v1, double[] v2) { 1831 final int mindim = (v1.length <= v2.length) ? v1.length : v2.length; 1832 // Essentially, we want to compute this: 1833 // v1.transposeTimes(v2) / (v1.euclideanLength() * v2.euclideanLength()); 1834 // We can just compute all three in parallel. 1835 double s = 0, e1 = 0, e2 = 0; 1836 for(int k = 0; k < mindim; k++) { 1837 final double r1 = v1[k], r2 = v2[k]; 1838 s += r1 * r2; 1839 e1 += r1 * r1; 1840 e2 += r2 * r2; 1841 } 1842 for(int k = mindim; k < v1.length; k++) { 1843 final double r1 = v1[k]; 1844 e1 += r1 * r1; 1845 } 1846 for(int k = mindim; k < v2.length; k++) { 1847 final double r2 = v2[k]; 1848 e2 += r2 * r2; 1849 } 1850 double a = FastMath.sqrt((s / e1) * (s / e2)); 1851 return (a < 1.) ? a : 1.; 1852 } 1853 1854 /** 1855 * Compute the cosine of the angle between two vectors, 1856 * where the smaller angle between those vectors is viewed. 1857 * 1858 * @param v1 first vector 1859 * @param v2 second vector 1860 * @param o Origin 1861 * @return cosine of the smaller angle 1862 */ 1863 public static double angle(double[] v1, double[] v2, double[] o) { 1864 final int mindim = (v1.length <= v2.length) ? v1.length : v2.length; 1865 // Essentially, we want to compute this: 1866 // v1' = v1 - o, v2' = v2 - o 1867 // v1'.transposeTimes(v2') / (v1'.euclideanLength()*v2'.euclideanLength()); 1868 // We can just compute all three in parallel. 1869 double s = 0, e1 = 0, e2 = 0; 1870 for(int k = 0; k < mindim; k++) { 1871 final double ok = (k < o.length) ? o[k] : 0; 1872 final double r1 = v1[k] - ok, r2 = v2[k] - ok; 1873 s += r1 * r2; 1874 e1 += r1 * r1; 1875 e2 += r2 * r2; 1876 } 1877 for(int k = mindim; k < v1.length; k++) { 1878 final double ok = (k < o.length) ? o[k] : 0; 1879 final double r1 = v1[k] - ok; 1880 e1 += r1 * r1; 1881 } 1882 for(int k = mindim; k < v2.length; k++) { 1883 final double ok = (k < o.length) ? o[k] : 0; 1884 final double r2 = v2[k] - ok; 1885 e2 += r2 * r2; 1886 } 1887 double a = FastMath.sqrt((s / e1) * (s / e2)); 1888 return (a < 1.) ? a : 1.; 1889 } 1890 } 1891