{"id":307,"date":"2023-05-29T17:26:10","date_gmt":"2023-05-29T15:26:10","guid":{"rendered":"https:\/\/intsight.com\/?p=307"},"modified":"2023-05-29T17:26:10","modified_gmt":"2023-05-29T15:26:10","slug":"multiplicar-por-la-traspuesta","status":"publish","type":"post","link":"https:\/\/intsight.com\/index.php\/2023\/05\/29\/multiplicar-por-la-traspuesta\/","title":{"rendered":"Multiplicar por la traspuesta"},"content":{"rendered":"

Una operaci\u00f3n muy<\/span> frecuente con matrices consiste en multiplicar una matriz por la traspuesta de otra. La implementaci\u00f3n m\u00e1s sencilla de esto ser\u00eda trasponer la segunda matriz y luego multiplicar la primera matriz por la traspuesta. Lamentablemente, trasponer una matriz es poco eficiente. No hay un patr\u00f3n sencillo de acceso a la cach\u00e9 que sea bueno al mismo tiempo: hay que descomponer la matriz en trozos peque\u00f1os… en pocas palabras, un l\u00edo. Y resulta que hay una forma m\u00e1s sencilla de conseguirlo: invertir la posici\u00f3n de los \u00edndices al acceder a la segunda matriz. El c\u00f3digo \u00abna\u00efve\u00bb para la multiplicaci\u00f3n directa de dos matrices se resum\u00eda en un triple bucle:<\/p>\n

for (int i = 0; i < m; i++)\n    for (int j = 0; j < p; j++)\n    {\n        double d = 0;\n        for (int k = 0; k < n; k++)\n            d += a[i, k] * b[k, j];\n        result[i, j] = d;\n    }<\/pre>\n
En la entrada sobre multiplicaci\u00f3n de matrices<\/a>, invert\u00edamos el orden de los dos bucles interiores para mejorar el rendimiento de la cach\u00e9 de memoria. Adem\u00e1s, a\u00f1ad\u00edamos punteros e instrucciones AVX. Para la nueva rutina, lo que invertimos son los \u00edndices de la segunda matrix y, en consecuencia, renunciamos al truco de intercambiar los bucles internos. Perdemos algo de velocidad pero, en cualquier caso, el resultado es mejor que trasponer expl\u00edcitamente y luego multiplicar.<\/p>\n
La rutina que finalmente est\u00e1 incluida en Austra<\/a> es la siguiente:<\/p>\n
public unsafe Matrix MultiplyTranspose(Matrix m)\n{\n    Contract.Requires(IsInitialized);\n    Contract.Requires(m.IsInitialized);\n    if (Cols != m.Cols)\n        throw new MatrixSizeException();\n    Contract.Ensures(Contract.Result<Matrix>().Rows == Rows);\n    Contract.Ensures(Contract.Result<Matrix>().Cols == m.Rows);\n\n    int r = Rows;\n    int n = Cols;\n    int c = m.Rows;\n    double[,] result = new double[r, c];\n    fixed (double* pA = values, pB = m.values, pC = result)\n    {\n        int lastBlockIndex = n & CommonMatrix.AVX_MASK;\n        double* pAi = pA;\n        double* pCi = pC;\n        for (int i = 0; i < r; i++)\n        {\n            double* pBj = pB;\n            for (int j = 0; j < c; j++)\n            {\n                int k = 0;\n                double acc = 0;\n                if (Avx.IsSupported)\n                {\n                    Vector256<double> sum = Vector256<double>.Zero;\n                    for (; k < lastBlockIndex; k += 4)\n                        sum = Avx.Add(\n                            left: Avx.Multiply(\n                                left: Avx.LoadVector256(pAi + k),\n                                right: Avx.LoadVector256(pBj + k)),\n                            right: sum);\n                    sum = Avx.HorizontalAdd(sum, sum);\n                    acc = sum.ToScalar() + sum.GetElement(2);\n                }\n                for (; k < n; k++)\n                    acc += pAi[k] * pBj[k];\n                pCi[j] = acc;\n                pBj += n;\n            }\n            pAi += n;\n            pCi += c;\n        }\n    }\n    return result;\n}\n<\/pre>\n
Una parte importante del truco es hacer que el lenguaje que implementa Austra reconozca la multiplicaci\u00f3n por la traspuesta y sepa usar la operaci\u00f3n m\u00e1s eficiente. Pero eso es f\u00e1cil de conseguir, y lo explicar\u00e9 en otro momento.<\/p>\n","protected":false},"excerpt":{"rendered":"
Una operaci\u00f3n muy frecuente con matrices consiste en multiplicar una matriz por la traspuesta de otra. La implementaci\u00f3n m\u00e1s sencilla de esto ser\u00eda trasponer la segunda matriz y luego multiplicar la primera matriz por la traspuesta. Lamentablemente, trasponer una matriz es poco eficiente. No hay un patr\u00f3n sencillo de acceso a la cach\u00e9 que sea […]<\/p>\n","protected":false},"author":1,"featured_media":308,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[15,19,20,23],"class_list":["post-307","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c","tag-algorithms","tag-linear-algebra","tag-matrices","tag-simd"],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/intsight.com\/wp-content\/uploads\/2020\/07\/yy.png?fit=350%2C350&ssl=1","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts\/307","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/comments?post=307"}],"version-history":[{"count":11,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts\/307\/revisions"}],"predecessor-version":[{"id":1180,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/posts\/307\/revisions\/1180"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/media\/308"}],"wp:attachment":[{"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/media?parent=307"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/categories?post=307"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/intsight.com\/index.php\/wp-json\/wp\/v2\/tags?post=307"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}