Oh, dann war ich etwas verwirrt

Ich hatte es jetzt so verstanden, dass es Debug war. In diesem Falle musst du Release mit Debuginformationen bauen und jeweils einen Profiler draufwerfen. Anders wirst du hier nicht weiterkommen.
Man kann natürlich 3 Tage auf den Code schauen und überlegen und eventuell die Stelle
raten. Zuverlässig in einer konstant abschätzbaren Zeit kommst du aber nur mit Profiler weiter.
Potenzielle Ideen wären Speicherallokierung (wobei Faktor 3-4 sehr krass wäre), vielleicht aber auch schon z.B. die Default-Optimierungsflags. Unter Windows z.B. ohne SSE, unter Linux mit; Angabe des Prozessortyps zum besseren Caching etc. Unbedingt auch mal die Aktivierung von intrinsic functions auf beiden Plattformen checken. Inlining sollte im Releasefall aktiv sein, trotzdem mal prüfen. Wenn das ganze gleitkommalastig ist, auch auf die diversen Flags checken (IEEE754 strict mode vs. relaxed, und das alles).
Ist die Hardwareplattform auf Windows und Linux dieselbe? Evtl. hilft die auch ein Cache-Profile weiter. Wenn's unter Windows Cache-Misses hagelt, wäre das ein guter Kandidat.
Btw, noch eine Idee. Führ das Programm mal unter Linux mit
time aus und schau mal wieviel Zeit es im User- und im System-Mode verbringt. Hängt natürlich von der Gesamtlaufzeit ab, deshalb ist es schwer zu sagen wieviel Zeit im Systemmode sein "darf". Aber bei einem Verhältnis von weniger als 1000/1 (ganz grob geraten) ist es ziemlich wahrscheinlich, dass es an Systemaufrufen liegt. Poste doch mal sonst das Ergebnis bei Unsicherheit.
Und nochwas

Lässt sich der umgebende Code soweit reduzieren, dass das Testobjekt möglichst nur noch aus der betreffenden Klasse besteht? (falls das möglich ist und du das eh nicht schon getan hast) Das vereinfacht das Finden des Problems enorm.
Ohne Profiler könnte man sonst auch hier sukzessive Code ausbauen und im Trial und Error Verfahren sich immer weiter annähern. Sofern der Code das wieder zulässt natürlich.
Und noch ein Nachtrag *g* Die Eingangsparameter des Algorithmus überprüfen. Manchmal liegt garnicht dort der Hund begraben wo du ihn vermutest, sondern dass der Algorithmus durch Rahmenbedingungen mit anderen Daten gefüttert wird. Versuch mal sicherzustellen, dass das auf beiden Plattformen gleich ist.
Noch eine Idee. Die letzte für heute

Ist der Code komplett neu? Oder ist dir das jetzt erst aufgefallen? Sonst erstmal Vorgängerversionen auschecken und prüfen oder das Problem dort auch so auftritt. Falls nicht - annähern und die Versionsunterschiede untersuchen.
Btw, wildes Raten und Ändern was Schuld sein könnte, ist i.A. Zeitverschwendung.
Wenn das alles nichts hilft, versuch ein minimalistisches Beispiel zu konstruieren, was das Problem zuverlässig reproduziert. Das war jetzt ein ganzer Haufen Zeug. *g* Sag mal Bescheid, welche Erfolge du verbuchen konntest.
